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

양방향 연결리스트와 연결리스트의 차이

연결리스트는 앞의 노드가 뒤쪽으로만 연결이 되었다면, 양방향 연결리스트는 앞과 뒤 양쪽으로 연결이 되어 노드의 이동이 더 자유롭다. 노드가 앞뒤로 연결되어 있기 때문에 head와 tail 모두 dommy 노드가 존재한다.

장점

양방향 연결구조로 노드를 탐색하는 방향이 양방향이라는 장점이 있다.

단방향 연결리스트는 맨 마지막에 위치한 데이터를 탐색하기 위해서 head에서 부터 시작하여 순차적으로 방문하며 탐색하지만, 이중 연결리스트는 그럴 필요가 없다.

리스트 처음과 끝에 dummy node를 존재시키면, 데이터를 담고 있는 node들은 모두 같은 모양이 되어 코드 작성에 용이하다.

 

단점

단방향 연결리스트에비해 링크를 더 갖고 있기때문에 링크를 나타내기 위한 메모리 사용량이 늘어난다.

원소를 삽입/삭제하는 연산에 있어서, 앞/뒤 링크를 모두 조정해야 하기 때문에 구조가 조금 더 복잡하다.

 

양방향 연결리스트 파이썬 구현

1) 노드 생성 및 삽입

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

class DoublyLinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None) # 추가
        self.tail = Node(None) # 추가
        self.head.prev = None
        self.head.next = self.tail # 추가
        self.tail.prev = self.head # 추가
        self.tail.next = None
        
    def getAt(self, pos):
    	if pos < 0 and pos > self.nodeCount:
        	return None
       
        if pos > self.nodeCount // 2:
        	i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
            	curr = self.tail.prev
                i += 1
        else:
            i = 0
        	curr = self.head
            while i < pos:
            	curr = self.next
                i += 1
        
        return curr
        
    def insertAt(self, pos, newNode):
    	if pos < 1 or pos > self.nodeCount + 1:
        	return False
        prev = self.getAt(pos - 1)
		return self.insertAfter(prev, newNode)
        
    def insertAfter(self, prev, newNode):
    	next = prev.next
        newNode.next = next
        newNode.prev = prev
        next.prev = newNode
        prev.next = newNode
        self.nodeCount += 1
        
        return True
        
    def insertBefore(self, next, newNode):
        newNode.prev = next.prev
        newNode.next = next
        next.prev = newNode
        newNode.prev.next = newNode
        self.nodeCount += 1
        return True

 

1. Node
   1. 단방향 연결리스트의 Node에서 prev 속성이 추가되었다.
   2. next와 prev를 통해 연결리스트의 앞과 뒤의 Node를 이동할 수 있다.
2. DoublyLikedList
   1. 생성자 속성 self.head와 self.tail에 Node(None)이 생겼다.
      양방향 연결리스트에서는 양 끝에 더미노드를 두기 때문에 처음과 끝을 Node(None)으로 둔 것이다.
   2. self.head.next와 self.tail.prev는 연결리스트에 아무것도 없을 때, 서로를 가르키게 한다.
3. getAt() 함수는 양방향 연결리스트의 원소를 얻어낸다.
   1. pos(구하려는 위치)가 전체 노드 개수(self.nodeCount)보다 많으면 뒤에서 부터 구한다.
      이 때, pos - self.nodeCount+1을 해주는 다음과 같다.
      노드를 [ ]로 칭하고, nodeCount = 8이면 리스트는 다음과 같이 표현된다.
      head(None) [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] tail(None)
      
      이러한 모양이 나오는 이유는 insert를 할 때만 nodeCount가 증가하여, 
      nodeCount는 head와 tail을 제외하게된다. (자리차지를 하는 dummy)
      
      예를 들면 pos가 6일 때, 실행되는 방식은 다음과 같다.
      [ ] 1 2 3 4 5 6 7 8 [ ]
      
      i = 0
      count = 8
      pos = 6
      count - pos = 2
      result = 8
      
      i = 1
      count = 8
      pos = 6
      count - pos = 2
      result = 7
      
      6을 꺼내기 전 7에서 멈추기 때문에, count - pos에 + 1를 해줘서 dummy까지 넘긴다.
   2. 처음부터 구할 때는 단방향리스트와 같이 구현한다.
4.  insertAt()에서 prev를 주는 이유는 insertAfter()를 호출하는지, insertBefore()를 호출하는지에 따라 구현이 다르다.

 

2)  노드 출력

class DoublyLinkedList:

     ㆍㆍㆍ
     
	def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result
        
    def reverse(self):
       	result = []  
      	curr = self.tail
      	while curr.prev.prev:
        	curr = curr.prev
        	result.append(curr.data)

     	 return result
        
        
# 노드 생성
node1 = Node(1)
node2 = Node(3)
node3 = Node(8)

# 노드 삽입
link = DoublyLinkedList()
link.insertAt(1, node1)
link.insertAfter(node1, node3)
link.insertAfter(node3, node2)

# 노드 출력
print(link.traverse()) # [1, 8, 3]
print(link.reverse()) # [3, 8, 1]

1. traverse()함수를 통해, 노드를 출력한다.
   단방향연결리스트와 다르게 curr.next에 .next가  더 붙는다. head와 tail에 dummy Node가 들어있기 때문이다.
2. reverse() 함수 또한 노드를 출력한다. 단, 양방향연결리스트의 끝에서부터 처음으로 출력한다.

 

3) 노드 삭제

class DoublyLinkedList:

    ㆍㆍㆍ

    def popAfter(self, prev):
        curr = prev.next
        prev.next = curr.next
        curr.next.prev = curr.prev
        self.nodeCount -= 1
        
        return curr.data

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

1. popAt() 함수에서 삭제할 pos번째를 받아 삭제한다.
   1. pos가 LinkedList의 범위를 벗어나면 IndexError가 나타난다.
   2. getAt()을 통해 현재위치-1(prev는 이전을 뜻함, popAfter에서 pos가 아닌 prev를 필요로하기때문에 -1을 한다.)
2. popAfter()함수에서 popAt()에서 넘겨받은 값을 삭제한다.
   1. Node가 1 -> 2 -> 3 일 때, 2를 제거한다면, 먼저 삭제하려는 현재를 위치를 찾는다. (curr = prev.next)
   2. prev.next를 이용해 현재 노드의 다음을 가르킨다. (prev.next = curr.next)
   3. curr.next가 없다면 클래스의 생성자인 tail에 prev를 넣고, 총개수-1을 해준다.