CS/자료구조

python으로 LinkedList 만들기

Timha 2023. 8. 30. 21:40

원티드 프리온보드 인턴쉽과정을 학습하면서 링크드 리스트를 배우고 나서 파이썬으로 구현해봤다.

 

처음에는 직접 리스트를 만든다는게 감이 잘 안왔지만 수업을 보면서 리스트가 어떻게 이뤄지고 어떤 형식으로 움직이는지 알게되고나니 생각보다 만들기 어렵지 않았다.

 

 

 

기본적인 리스트는 head 하나를 가지며 리스트의 헤드를 통해서 각 노드를 순회 할 수 있다.

 

Node에 데이터를 넣을 data와 next를 통해서 데이터와 다음노드방향을 알려준다.

 

<코드 본문 >

class Node:
    def __init__(self,data): 
        self.data = data # 노드값 
        self.next = None # 최초 생성시 다음 노드 지정안함

class LinkedList:
    def __init__(self,data): # 최초 링크드리스트 사용시 헤더 생성
        self.head = Node(data)

    def append(self,data):
        cur = self.head  # 현재 리스트의 헤드(시작점) 찾기
        while cur.next is not None: # 마지막 다음 목적지가 NOne값이 나올떄까지 반복
            cur= cur.next
        cur.next = Node(data) # 마지막 노드와 현재 추가하려는 노드 연결 

    def find_index(self,data):  #값으로 인덱스 찾기
        now =self.head # 헤드부터 시작해서 data값과 동일한 값 찾기 
        cnt=0
        while now == data:  # 동일한값을 찾는ㄴ다면 정지 
            if now.data ==data:
                break
            cnt+=1
            now = now.next
        print(cnt)
    def get_node(self,data): #인덱스 노드 위치 찾기
        now = self.head #리스트의 헤드 찾기
        cnt =0
        while now>data:
            now =now.next
            cnt+=1
        return cnt
    def insert_node(self,index,data): #노드 삽입
        new_node = Node(data)
        if index==0:  # 헤드변경 
            new_node.next = self.head
            self.head = new_node
            return
        find_node= self.get_node(index-1) # 찾을 인덱스의 전 인덱스 찾기 
        new_node.next =  find_node.next # 생성된 노드의 next를 전 인덱스의 next로 변경
        find_node.next = new_node # 찾은 인덱스 -1 의 next를 생성된 노드로 지정 
        
    def delete_node(self,index):
        if index ==0:
            self.head = self.head.next
            return
        find_node =self.get_node(index-1) # 인덱스-1 를 찾은 후 현재 인덱스의 앞의 연결된 부분을 연결
        find_node.next = find_node.next.next # 인덱스 next변경해줌

 

이번주에 나온 과제중 stack을 만드는 문제가 있었는데  먼저 링크드 리스트를 만들고나니 한결 쉽게 풀 수 있었다.