[Data] 자료 구조란?(2) : 링크드 리스트, 더블리 링크드 리스트, 접근, 탐색, 삽입, 삭제 시간 복잡도

 

 

💡 링크드 리스트 Linked List : 연결 리스트

• 데이터가 저장된 노드들을 연결해 만든 자료 구조
• 데이터를 순서대로 연결, 실제 메모리엔 흩어져 있다.
• 요소 추가 가능
• 구현 방식이 동적 배열보다 더 복잡, 상황에 따라 사용

1, 2, 3 데이터를 apple, banana, cherry 이 세 노드에 담을 때 순서를 어떻게 정하는지 구조를 살펴보면,

1 - 2 - 3 ➡️ apple: 1/banana - banana: 2/cherry - cherry: 3(다음 이름이 없으므로 마지막 노드)

이런 식으로 다음 노드의 이름을 표시해 순서대로 연결하는 것을 볼 수 있다.

 

💡 노드 : 하나의 객체로, data 와 next(다음 노드의 레퍼런스) 로 구성

// n_1 데이터를 n_2 데이터와 연결
n_1.next = n_2 // = n_2 에 대한 레퍼런스

 

첫 번 째 노드는 head 노드!

 

링크드 리스트 접근 연산 : 특정 위치에 있는 노드를 리턴하는 연산, 헤드노드부터 차례대로 확인한다.

링크드 리스트 접근 시간 복잡도 : O(n), 인덱스 x 에 있는 노드에 접근하려면 헤드부터 다음 노드로 x 번 이동한다.

탐색 연산도 마찬가지

 

링크드 리스트 삽입 연산

# 마지막 순서에 삽입할 때 : if previous_node is self.tail O(1+1)
self.tail.next = new_node
self.tail = new_node

# 두 노드 사이에 삽입할 때 : 위 조건의 else O(n+1)
new_node.next = previous_node.next
previous_node.next = new_node

# 맨 앞에 넣을 때 O(1+1)
new_node = Node(data)
new_node.next = self.head
self.head = new_node
        
if self.tail is None: # 리스트가 비어 있는 경우
	self.tail = new_node

 

링크드 리스트 삭제 연산

data = previous_node.next.data

# 테일 노드를 삭제할 때 : if previous_node.next is self.tail O(n+1)
previous_node.next = None # 그냥 연결을 끊는다.
self.tail = previous_node.next

# 두 노드 사이 노드를 지울 때 : 위 조건의 else O(n+1)
previous_node.next = previous_node.next.next

return data # 지운 데이터를 return

 

💡 더블리 링크드 리스트 Doubly Linked List : prev, next 레퍼런스를 모두 가진 노드 리스트

더블리 링크드 리스트 추가 연산

new_node = Node(data)

# 링크드 리스트가 비어 있는 경우 : if self.head is None O(1+1)
self.head = new_node
self.tail = new_node

# 링크드 리스트에 데이터가 이미 있는 경우, 맨 뒤에 삽입할 때 : 위 조건의 else, if previous_node is tail O(1+1)
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new.node

 

더블리 링크드 리스트 삽입 연산

# 두 노드 사이에 삽입할 때 : 위 조건의 else O(n)
new_node.prev = previous_node
new_node.next = previous_node.next
previous_node.next.prev = new_node
previous_node.next = new_node

# 맨 앞에 삽입할 때 O(1+1)
if self.head is None: # 리스트가 비어있다면
    self.head = new_node
    self.tail = new_node

else:
    new_node.next = self.head # 새로운 노드의 다음 노드를 head 노드로 지정
    self.head.prev = new_node # head 노드의 전 노드를 새로운 노드로 지정
    self.head = new_node # head 노드 업데이트

 

더블리 링크드 리스트 삭제 연산

# 지우려는 노드가 리스트에 남은 마지막 노드일 때, head 와 tail 이 같은 경우 : if self.tail == self.head O(1+1)
self.head = None
self.tail = None

# 여러 노드가 있는 리스트에서 head 노드를 지울 때 : elif self.head == node_to_delete O(1+1)
self.head = self.head.next
self.head.prev = None

# 여러 노드가 있는 리스트에서 tail 노드를 지울 때 : elif self.tail == node_to_delete O(1+1)
self.tail = self.tail.prev
self.tail.next = None

# 두 노드 사이에 있는 노드를 지울 때 : else O(n)
node_to_delete.prev.next = node_to_delete.next
node_to_delete.next.prev = node_to_delete.prev

 

더블리 링크드 리스트 연산 시간 복잡도

연산	링크드 리스트
접근	O(n)
탐색	O(n)
삽입	O(n+1) or O(1)
삭제	O(n+1) or O(1)

 

두 링크드 리스트의 차이점

• 싱글리 링크드 리스트
  • 뒤 노드에만 접근 가능
  • 노드마다 실제 데이터와 뒤 노드 레퍼런스 저장, O(n) 공간 사용 (O(n-1))
  • 공간을 효율적으로 활용하고싶다면 링크드 리스트 활용
• 더블리 링크드 리스트
  • 앞 ,뒤 노드 모두 접근 가능하므로 어떤 노드던 모든 노드에 접근 가능
  • 노드마다 실제 데이터와 앞, 뒤 노드 레퍼런스 저장, O(n) 공간 사용(하지만 실제론 두배 2n-2)
  • tail 노드를 많이 삭제해야 한다면 더블리 리스트를 활용 (싱글: O(n+1), 더블: O(1+1))

연산	싱글리 링크드 리스트	더블리 링크드 리스트
가장 앞에 접근 + 삽입	O(1+1)	O(1+1)
가장 앞에 접근 + 삭제	O(1+1)	O(1+1)
가장 뒤에 접근 + 삽입	O(1+1)	O(1+1)
가장 뒤에 접근 + 삭제	O(n+1)	O(1+1)