2. Linked List - 파이썬 연결리스트 공부하기

Linked List

• 개별적으로 위치하고 있는 원소의 주소를 연결한 선형 자료구조
• 링크를 통해 워소에 접근하므로, 물리적인 순서를 맞추는 작업이 필요없음
• 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능
• 탐색 - 순차탐색 O(n)
• 특정 노드 주변에서 삭제, 추출 - O(1)

 

주의할 점

1. head를 변경할 때 주의
2. 연결리스트를 종주할 때, 찾으려는 값이 연결리스트에 없는 경우에 대한 생각
3. 찾으려는 값이나 파라미터로 들어온 node가 head인 경우에 대한 생각

 

연결리스트로 스택 구현

2021.07.07 - [CS study/Data Structure] - 1. Stack - 파이썬 스택 공부하기

1. Stack - 파이썬 스택 공부하기

 

파이썬 코드구현

가장 먼저 Node와 BinaryTree 클래스의 기본 골격을 생성한다.

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

삽입

    # 연결 리스트의 가장 앞 부분에 삽입
    def addtoFirst(self, item):
        if self.head is None:
            self.head = Node(item, None)
        else:
            self.head = Node(item, self.head)

    # 연결 리스트의 가장 끝 부분에 삽입
    def addtoLast(self, item):
        if self.head is None:
            self.head = Node(item, None)
        else:
            elem = self.head
            while elem.next:
                elem = elem.next
            elem.next = Node(item, None)

    # 특정 연결 리스트(node)의 뒤에 item 삽입
    def addtoNext(self, node, item):
        node.next = Node(item, node.next)

    # 특정 연결 리스트(node)의 앞에 삽입
    def addtoPrev(self, node, item):
        elem = self.head
        if node == elem:
            self.addtoFirst(item)
            return
        while elem.next != node:
            elem = elem.next
        elem.next = Node(item, elem.next)

삭제

    # 특정 연결 리스트의 다음 노드 삭제
    def deletetoNext(self, node):
        if node is None or node.next is None:
            pass
        else:
            node.next = node.next.next

    # i 번쨰 연결 리스트 삭제
    def delete(self, i):
        if i == 0:
            self.head = self.head.next
        else:
            node = self.head
            for _ in range(i-1):
                node = node.next
            node.next = node.next.next

추출

    # i 번째 연결 리스트의 값을 리턴
    def get(self, i):
        node = self.head
        for _ in range(i):
            node = node.next
        print(node.item)
        return node.item
        
    # value라는 item을 갖는 노드 찾기
    def find(self, value):
        elem = self.head
        while elem != None and elem.item != value:
            elem = elem.next
        return elem