양방향 연결리스트 (Doubly Linked List) in Python

연결리스트의 장점은 삽입과 삭제가 비교적 배열에 비해 자유롭다는 것이다.

그런데 왜 link는 한 쪽에 만 존재하고, 한 방향으로만 이동할수 있는 걸까? 뒤에서 앞으로 이동할 순 없는걸까?

 

 이 문제를 해결하기 위해 양방향 연결리스트가 등장했다.

 

---

1. 노드의 구조

 

class Node:
    def __init__(self,item):
        self.data = item
        self.prev = None #새로 추가 된 앞으로 가는 링크
        self.next = None

 

 앞으로 가는 링크 prev가 추가됐다. 노드를 초기화할 땐  prev, next 모두 None으로 초기화해주자.

 

 

2. 양방향 연결리스트의 구조 -> 처음과 끝에 Dummy Node 추가!

 이제 뒤에서도 앞으로 이동이 가능하므로, tail을 가리키는 dummy node도 추가하자. 

이렇게 되면 데이터를 담고 있는 노드들은 모두 같은 모양을 이루고, 코드 작성이 더 간결해진다.

 

class DoublyLinkedList:
    def __init__(self,item):
        self.nodeCount=0
        self.head = Node(None) #head dummy node 초기화
        self.tail = Node(None) #tail dummy node 초기화
        self.head.prev = None
        self.head.next = self.tail #아무것도 없을 때 head와 tail을 서로를 가리킴
        self.tail.prev = self.head
        self.tail.next = None

 

 

3. 리스트 순회

 

def traverse(self):
    result = []
    curr = self.head
    while curr.next.next:#curr.next가 tail이 되기전까지
    	curr = curr.next #맨 마지막 노드가 아니라면 그 다음노드로 이동
        result.append(curr.data)
    return result

 

4. 리스트 역순회

 

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

 

비어있는 리스트에 대해서도 유효하다.

 

 

5. 원소의 삽입

 

1. New Node의 prev, next에 각 노드 연결
2. 다음 노드의 prev에 NewNode 연결
3. 이전 노드의 next에 NewNode 연결
4. 노드의 개수 1 추가

 

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)

 

1) 처음부터 삽입

 

def insertAfter(self,prev,newNode):
    next = prev.next
    newNode.prev= prev
    newNode.next = next
    prev.next = newNode
    next.prev = newNode
    self.nodeCount +=1
    return True

 

2)뒤에서부터 삽입

    def insertBefore(self, next, newNode):
        #next의 앞에 newNode 삽입
        #newNode부터 이어주기
        newNode.next  = next
        newNode.prev = next.prev
        #앞 뒤 이어주기
        next.prev.next = newNode
        next.prev = newNode
        self.nodeCount+=1
        return True

 

 

6. 특정 원소 얻어내기

 

기존의 코드

def getAt(self,pos):
    if pos<0 or pos>self.nodeount:
        return None
    i=0
    curr = self.head
    while i<pos:
        curr = curr.next
        i+=1
    return curr

양방향 연결리스트에 맞춰 개선된 코드

def getAt(self,pos):
    if pos<0 or pos>self.nodeCount:
        return None
    if pos>self.nodeCount//2: #뒷쪽에 있을 경우 뒤에서부터 탐색
        i=0
        curr = self.tail
        while i<self.nodeCount-pos+1: #tail에서부터 시작해서, pos가 tail에서 떨어진 만큼 이동
            curr = curr.prev
            i+=1
        else:
            #앞에서부터 탐색하는 while문

 

7. 특정 원소 삭제

 

1) 특정 노드 뒤의 원소 삭제

2) 특정 노드 앞의 원소 삭제

 

    def popAfter(self, prev):
        #prev 이후의 원소 반환
        curr = prev.next
        prev.next = curr.next
        curr.next.prev = prev
        self.nodeCount-=1
        return curr.data


    def popBefore(self, next):
        #next 앞의 원소 반환
        curr = next.prev
        curr.prev.next = next
        next.prev = curr.prev
        self.nodeCount-=1
        return curr.data


    def popAt(self, pos):
        #pos 범위 검사 해서 pop 때림
        if pos<1 or pos>self.nodeCount:
            raise IndexError
        else:
            #다음 원소 삭제
            return self.popAfter(self.getAt(pos-1))

 

head, tail을 다른 노드를 가리키는 포인터가 아닌, 또 하나의 노드로 두니, head와 tail도 노드 추가나 삭제의 과정에서 다른 노드들과 같은 취급을 해도 문제가 없었고, 그만큼 예외처리할 것이 줄어들어 더 원활하게 함수를 짤 수 있었다. 메모리나 구조가 다소 복잡하지만, 알고리즘이 더 간단하고 직관적으로 변한다는 장점이 있다는 것을 느낄 수 있었다.