Post

[자료구조] 7. 양방향 연결리스트 (Doubly Linked Lists)

Posted
By Jihyun,Ryu 14 min read

양방향 연결 리스트 (Doubly Linked Lists)

  • 지금까지 다루었던 연결 리스트의 경우에는 앞에서 뒤로만 진행이 가능하였다.
    하지만, 양방향 연결 리스트의 경우 앞으로도 뒤로도 진행이 가능하다.
    즉, 단방향이 아니라 양방향으로 진행이 가능하다.


  • 양방향 연결 리스트는 이전 연결 리스트와 달리 양방향으로 진행이 가능하기 때문에 이전 Node와 달리 이전(prev) 노드에 대한 주소를 할당하는 포인터를 추가할 필요가 있다. 따라서, 기존 Node클래스에 self.prev인스턴스 변수를 추가한다.

    1
2
3
4
5

      class Node:
      def __init__(self, item):
          self.data = item # 노드가 담고 있는 데이터 원소
          self.prev = None # *이전 노드에 대한 정보를 담고 있는 포인터
          self.next = None # 다음 노드에 대한 정보를 담고 있는 포인터


  • 양방향 연결 리스트의 경우 Head외에도 더미 테일 노드(Dummy Tail Node)를 배치시켜 모든 방향에서의 비효율성 문제를 극복할 수 있다. 더불어, 더미 노드외의 유효한 노드들의 경우 전부 같은 일관된 형태를 가져 코드를 구성하는데 있어서 편의성이 도모된다. 예를 들어, Head 더미 노드만 있었을 경우에는 Tail의 조정이 필요한 경우가 있었지만, Tail 더미 노드가 추가된 지금에는 Tail 더미 노드에 대한 조정 및 예외 처리 등에 관한 피로도가 이전보다 낮아졌다.



    따라서, 빈 양방향 연결 리스트의 경우에는 다음과 같이 클래스를 정의할 수 있다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

      from .node import Node
    
  class DoublyLinkedList:
      def __init__(self, item):
          self.nodeCount = 0
          self.head = Node(None)
          self.tail = Node(None)
          # Head노드의 포인터 정의
          self.head.prev = None
          self.head.next = self.tail
          # Tail노드의 포인터 정의
          self.tail.prev = self.head
          self.tail.next = None
        
      def traverse(self):
          """
          (Head -> Tail방향) 연결리스트의 노드 데이터 확인용 함수
          """
          result = []
          # 순회 시작점: Tail노드
          curr = self.head
          # curr.next로 조건 생성 시 Tail Dummy Node의 값도 반환됨
          # 더불어, 빈 리스트의 순회도 가능하게함
          while curr.next.next
                  curr = curr.next
                  result.append(curr.data)

          return result
        
      def reverse(self):
          """
          (Tail -> Head방향) 연결리스트의 노드 데이터 확인용 함수
          """
          result = []
          # 순회 시작점: Tail노드
          curr = self.tail
          # curr.next로 조건 생성 시 Tail Dummy Node의 값도 반환됨
          # 더불어, 빈 리스트의 순회도 가능하게함
          while curr.next.next
                  curr = curr.next
                  result.append(curr.data)

          return result


양방향 연결 리스트 핵심 연산

(1) 리스트 순회 (Traversal/Reverse)

  • 양방향 연결 리스트의 순회 연산은 Head뿐만 아니라 Tail에서도 시작이 가능하다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

      class Node:...
    
  class DoublyLinkedList:
      def __init__(self, item):...
        
      def traverse(self):
          """
          (Head -> Tail방향) 연결리스트의 노드 데이터 확인용 함수
          """
          result = []
          # 순회 시작점: Tail노드
          curr = self.head
          # curr.next로 조건 생성 시 Tail Dummy Node의 값도 반환됨
          # 더불어, 빈 리스트의 순회도 가능하게함
          while curr.next.next
              curr = curr.next
              result.append(curr.data)

          return result
        
      def reverse(self):
          """
          (Tail -> Head방향) 연결리스트의 노드 데이터 확인용 함수
          """
          result = []
          # 순회 시작점: Tail노드
          curr = self.tail
          # curr.tail로 조건 생성 시 Tail Dummy Node의 값도 반환됨
          # 더불어, 빈 리스트의 순회도 가능하게함
          while curr.tail.tail
              curr = curr.tail
              result.append(curr.data)

          return result


(2) N번째 특정 원소 탐색

  • 기존 탐색 함수의 경우 앞에서 부터 선형 탐색 과정이 이루어졌다. 이는 연결리스트 내에 위치한 노드의 수가 많아질수록 비효율적이다. 하지만, Head노드와 동일한 생김새를 가진 Tail노드를 고려했을 때, 위의 Reverse 순회 처럼 Tail부터 탐색이 진행되도록 구성될 수 있다. 하지만, 알고리즘의 타입 자체는 앞에서 시작하나 뒤에서 시작하나 선형 시간 알고리즘에 해당하는 것은 동일하다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

      from .node import Node
    
  class DoublyLinkedList:
      def __init__(self, item):...

      def traverse(self):...

      def reverse(self):...

      def getAt(self, pos):...
          """
          노드 탐색용 함수
          - pos: 탐색하고자하는 노드의 순서
          """
          if pos < 0 or pos > self.nodeCount:
              return None
            
          i = 0				

          # 탐색하는 위치가 중간보다 뒤일 때, Tail부터 탐색 시작
          if pos > self.nodeCount//2:
              curr = self.tail
              while i < self.nodeCount-pos+1:
                  curr = curr.prev
                  i +=1
            
          # 탐색하는 위치가 중간보다 앞일 때, Head부터 탐색 시작 
          else:	
              curr = self.head
              while i < pos:
                      curr = curr.next
                      i += 1
                    
          return curr
  
  if __name__ == '__main__':
      linkedlist = LinkedList()
      print(linkedlist.getAt(0)) # None


(3) 원소 삽입 (Insertion)

  • 양방향 연결리스트에서 원소의 삽입 과정은 다음의 절차를 따른다.
    (newNode: 새로 삽입할 노드, prevNode: newNode 앞에 위치할 노드, nextNode: newNode뒤에 위치할 노드, 삽입 이전 *prev뒤의 노드는 next이다.)

    1. newNode의 prev와 next 포인터에 각각 prevNode와 nextNode의 주소를 할당한다.
      • Tail노드가 유효했을 경우 수행했던 예외 처리를 수행할 필요가 없어졌다.
      • 즉, 단방향 연결 리스트보다 코드가 단순해졌다.

    2. prevNode의 next포인터에 newNode의 주소를 할당한다.
      nextNode의 prev포인터에 newNode의 주소를 할당한다.

    3. nodeCount(# of Node)를 1 증가시킨다.


  • 위의 원소 삽입 과정을 함수(insertAfter)로 표현하면 다음과 같다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

      def insertAfter(self, prevNode, newNode):
    
      nextNode = prevNode.next

      # 1번 과정 수행/
      newNode.prev = prevNode
      newNode.next = nextNode
        
      # 2번 과정 수행
      prevNode.next = newNode
      nextNode.prev = newNode

      # 3번 과정 수행
      self.nodeCount += 1

      return True


  • 원소의 삽입 위치를 고려했을 떄 함수(insertAt)는 다음과 같다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

      class Node:...
    
  class DoublyLinkedList:
      def __init__(self, item):...

      def traverse(self):...

      def reverse(self):...

      def getAt(self, pos):...
        
      def insertAfter(self, prevNode, newNode):

          nextNode = prevNode.next
            
          newNode.prev = prevNode
          newNode.next = nextNode
            
          prevNode.next = newNode
          nextNode.prev = newNode
            
          self.nodeCount += 1				
          return True
                
      def insertAt(self, pos, newNode):
                
          if pos <1 or pos > self.nodeCount+1:
              return False
            
          # 기존 Head Dummy Node와 함께 Tail Dummy Node가 추가되어
          # 단방향 연결리스트에서 고려된 예외 처리를 수행할 필요가 없어졌다.
          prevNode = self.getAt(pos).prev
          return self.insertAfter(prevNode, newNode)


(4) 원소의 삭제 (Deletion)

  • 양방향 연결리스트에서 원소의 삭제 과정은 다음의 절차를 따른다.
    (prevNode: 삭제할 노드 앞에 위치한 노드, nextNode: 삭제할 노드 뒤에 위치할 노드)

    1. prevNode의 next포인터에 nextNode의 주소를 할당한다.
      • Tail노드가 유효했을 경우 수행했던 예외 처리를 수행할 필요가 없어졌다.
      • 즉, 단방향 연결 리스트보다 코드가 단순해졌다.

    2. nextNode의 prev포인터에 prevNode의 주소를 할당한다.

    3. nodeCount(# of Node)를 1 감소시킨다.


  • 위의 원소 삭제 과정을 함수(popAfter)로 표현하면 다음과 같다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

      def popAfter(self, prevNode):
    		
      pop_value = prevNode.next.data
      nextNode = prevNode.next.next
    
      # 1번 과정 수행
      prevNode.next = nextNode
    
      # 2번 과정 수행
      nextNode.prev = prevNode
    
      # 2번 과정 수행
      self.nodeCount-=1
    
      return pop_value


  • 이때, 연결리스트의 원소 삭제 위치를 고려해서 함수(popAt)을 구현하면 다음과 같다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

      class Node:...
    
  class DoublyLinkedList:
      def __init__(self, item):...

      def traverse(self):...

      def reverse(self):...

      def getAt(self, pos):...
        
      def popAfter(self, prevNode):
                
          pop_value = prevNode.next.data
          nextNode = prevNode.next.next
        
          prevNode.next = nextNode
          nextNode.prev = prevNode

          self.nodeCount-=1		
          return pop_value
                
      def popAt(self, pos):
  
          if pos <= 0 or pos >= self.nodeCount+1:
              raise IndexError
    
          prevNode = self.getAt(pos).prev
    
          return self.popAfter(prevNode)


(5) 두 리스트 병합 (Concatenation)

  • 양방향 연결 리스트의 경우 단방향 연결 리스트와 달리 더미 테일 노드가 추가되면서 병합되는 두 연결리스트가 모두 비어있는지 혹은 둘 중 하나만 비어있는지 고려할 필요가 있다.
    (L1: 병합 시 앞에 위치한 연결리스트, L2: 병합 시 뒤에 위치한 연결리스트)

    • L1, L2모두 비어있거나, L2만 비어있는 경우: 병합 과정을 패스한다.

    • L1만 비어있는 경우: L1의 Head와 Tail을 각각 L2의 Head와 Tail로 교체한다.

    • L1, L2가 모두 비어있지 않는 경우

      1. L1.Tail 앞에 위치한 노드를 L2.Head 뒤에 위치한 노드의 prev포인터에 할당한다.
      2. L2.Head 앞에 위치한 노드를 L1.Tail 앞에 위치한 노드의 next포인터에 할당한다.


  • 위의 과정을 클래스 내 함수(concat)로 구현하면 다음과 같다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

      class Node:...
    
  class DoublyLinkedList:
      def __init__(self, item):...

      def traverse(self):...

      def reverse(self):...

      def getAt(self, pos):...
        
      def concat(self, L2):
          """
          L2: 기존 연결리스트에 부착할 연결리스트 객체
          """
          # ***L1, L2***모두 비어있거나, ***L2***만 비어있는 경우
          if L2.nodeCount == 0 or (self.nodeCount+L2.nodeCount==0):
              pass
                    
          # ***L1***만 비어있는 경우
          elif self.nodeCount == 0:
              self.head = L2.head
              self.tail = L2.tail
                    
          # ***L1, L2***가 모두 비어있지 않는 경우
          else:
              L1_Node = self.tail.prev
              L2_Node = L2.head.next
              L1_Node.next = L2_Node
              L2_Node.prev = L1_Node
              self.tail = L.tail
    
          self.nodeCount += L2.nodeCount
    
          return True


References

Data, Data Structure
Data Data Structure Linked Lists Doubly Linked Lists
This post is licensed under CC BY 4.0 by the author.