[자료구조] 연결 리스트(Linked List)

Sawol·2021년 4월 7일

백준 알고리즘 파이썬

algorithm & data structure

목록 보기

6/18

❗️ 계속해서 업데이트 될 예정...

잘못된 부분이 있다면 알려주세요 🙏

연결 리스트

연결 리스트란(Linked List)

배열과 함께 가장 기본이 되는 선형 자료구조 중 하나. 연결 리스트의 각 노드는 데이터와 다음 노드의 정보(링크)가 포함되어 있다.
첫번째 노드부터 순차적으로 접근해야하므로 이진 검색을 할 수 없다. 또한 노드에는 다음 노드의 참조를 위한 정보가 포함되어 있으므로 추가 메모리 공간이 필요하다.

배열과 차이

배열과 달리 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 편리하다. 다만, 이 때문에 특정 인덱스에 접근할 때 상수시간에 접근할 수 없다. 즉, 탐색에는 O(n)이 소요된다. 반면, 시작 또는 끝 점에 데이터를 추가, 삭제, 추출하는 작업은 O(1)에 가능하다.
데이터의 크기를 정확히 알 수 없을 때(매우 유동적일 때) 배열보다 연결리스트를 사용하는 것이 훨씬 효율적이다. 배열은 메모리를 모두 사용하지 않을지라도 큰 크기의 메모리를 할당해야하지만, 링크드 리스트는 데이터의 크기만큼 정확히 할당할 수 있다. 왜냐하면 시작, 끝점에 해당하는 데이터를 삭제, 추가 하는 작업은 O(1)로 가능하기 때문.

이중 연결 리스트(doubly linked list)

순방향 및 역방향 모두 순회 가능하다.
단일 연결 리스트는 노드를 삭제하려면 이전 노드에 대한 정보가 필요해 연결 리스트 전체를 순환하여 찾아야 했다. 하지만 이중 연결 리스트는 이전 노드에 대한 정보를 현재 노드도 갖고 있기 때문에 바로 삭제가 가능하다.
다만, 두 가지 포인터를 가지므로 추가 공간이 필요하다.

이중 연결 리스트 구현

노드 생성


# Node of a doubly linked list
class Node:
    def __init__(self, next=None, prev=None, data=None):
        self.next = next # reference to next node in DLL
        self.prev = prev # reference to previous node in DLL
        self.data = data

이중 연결 리스트에서 필요한 다음 노드에 대한 정보 next, 이전 노드에 대한 정보 preve, 데이터 data를 할당해준다.

헤드 노드 삽입

# Adding a node at the front of the list
def push(self, new_data):
 
    # 1 & 2: Allocate the Node & Put in the data
    new_node = Node(data = new_data)
 
    # 3. Make next of new node as head and previous as NULL
    new_node.next = self.head
    new_node.prev = None
 
    # 4. change prev of head node to new node
    if self.head is not None:
        self.head.prev = new_node
 
    # 5. move the head to point to the new node
    self.head = new_node

push 함수를 통해 노드의 제일 앞에 새로운 노드를 추가한다.
노드에 new_data를 삽입하여 새로운 노드를 만든다. 추가된 노드가 Head가 되므로 원래 Head노드가 새로 추가된 노드의 Next가 된다. Head 노드이므로 Prev노드는 존재하지 않는다.

연결 리스트 중간에 삽입

def insertAfter(self, prev_node, new_data):
 
    # 1. check if the given prev_node is NULL
    if prev_node is None:
        print("This node doesn't exist in DLL")	# DLL : Doubly Linked List
        return

    #2. allocate node  & 3. put in the data
    new_node = Node(data = new_data)

    # 4. Make next of new node as next of prev_node
    new_node.next = prev_node.next

    # 5. Make the next of prev_node as new_node
    prev_node.next = new_node

    # 6. Make prev_node as previous of new_node
    new_node.prev = prev_node

    # 7. Change previous of new_node's next node */
    if new_node.next is not None:
    	new_node.next.prev = new_node

새로 추가된 노드의 Next는 원래 존재했던 노드의 Next이다. 원래 존재했던 노드의 Next는 새로 추가된 노드로 바꿔야한다. 새로 추가된 노드의 Prev는 원래 존재했던 노드가 된다.

연결 리스트 끝에 삽입

def append(self, new_data):
 
      # 1. allocate node 2. put in the data
      new_node = Node(data = new_data)
      last = self.head
 
      # 3. This new node is going to be the
      # last node, so make next of it as NULL
      new_node.next = None
 
      # 4. If the Linked List is empty, then
      #  make the new node as head
      if self.head is None:
          new_node.prev = None
          self.head = new_node
          return
 
      # 5. Else traverse till the last node
      while (last.next is not None):
          last = last.next
 
      # 6. Change the next of last node
      last.next = new_node
      # 7. Make last node as previous of new node */
      new_node.prev = last

새로 추가된 노드가 마지막 노드이므로 Next를 None으로 설정한다. 만약 새로 추가된 노드가 연결 리스트의 유일한 노드이면 해당 노드의 Next와 Prev는 존재하지 않으므로 None으로 설정되고 Head가 새로 추가된 노드가 된다.
그리고 원래 끝에 있던 노드의 Next에 새로 추가된 노드와 연결하고 새로 추가된 노드의 Prev는 원래 끝에 있던 노드와 연결한다.

연결리스트 삭제

def deleteNode(self, dele):
         
     # Base Case
     if self.head is None or dele is None:
         return

     # If node to be deleted is head node
     if self.head == dele:
         self.head = dele.next

     # Change next only if node to be deleted is NOT
     # the last node
     if dele.next is not None:
         dele.next.prev = dele.prev

     # Change prev only if node to be deleted is NOT
     # the first node
     if dele.prev is not None:
         dele.prev.next = dele.next