[자료구조] 2. 링크드 리스트 - 2 더블 링크드 리스트

저번 글에서는 싱글 링크드 리스트에 대해서 공부하고 직접 구현해봤습니다.

2. 링크드 리스트 - 1 싱글 링크드 리스트

[자료구조] 2. 링크드 리스트 - 1 싱글 링크드 리스트

 

싱글 링크드 리스트는 앞쪽(헤드)에서 뒤쪽(테일)으로 한 방향으로만 연결된 리스트를 말했죠.

그래서 단순 연결 리스트라고도 불립니다.

이번에는 양쪽으로 연결되는 더블 링크드 리스트, 즉 이중 연결 리스트를 알아보도록 하겠습니다.

 

더블 링크드 리스트

 

 더블 링크드 리스트는 싱글 링크드 리스트와 달리 뒤쪽으로 가는 포인터 뿐만이 아니라 앞으로 가는 포인터를 가집니다.

싱글 링크드 리스트는 아래 그림과 같이 뒤로 가는 포인터인 next를 가지고 있었죠. 더블 링크드 리스트는 이 next와 함께 반대쪽, 즉 헤드쪽을 바라보는 prev라는 포인터를 가지게 됩니다.

싱글 링크드 리스트의 노드

 

 

 

왼쪽 그림은 싱글 링크드 리스트의 노드입니다.

노드의 값인 데이터(data)와

다음 노드에 대한 포인터인 next만을 가지고 있었죠

 

더블 링크드 리스트의 노드는 위에서 설명한 것처럼 두개의 포인터를 가집니다.

왼쪽은 이전 노드에 대한 포인터로 prev라고 부르겠습니다.

오른쪽은 기존과 같이 다음 노드에 대한 포인터인 next입니다.

---

노드 클래스

 원래 싱글 링크드 리스트에 있던 노드 클래스를 가져와 다음과 같이 수정합시다.

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

 

클래스 생성자

이제 DoublyLinkedList 클래스의 생성자를 만들어봅시다.

def __init__(self):
    self.head = self.Node(None)
    self.tail = self.Node(None, self.head)
    self.head.next = self.tail
    self.size = 0

전과 비슷하지만 헤드와 테일을 만들고 두 개를 연결시켜둔다는 점이 다릅니다.

싱글 링크드 리스트와 마찬가지로 사이즈 게터 함수(getSize)와 isEmpty 함수를 만들어보도록 합시다.

def isEmpty(self):
    return self.size == 0
    
def getSize(self):
    return self.size

 

노드 생성 및 노드 삭제

 createNode, 이것도 똑같이 노드를 생성만 하는 함수입니다.

def createNode(self, data):
    NewNode = self.Node(data)
    return NewNode

 deleteNode 함수도 마찬가지입니다.

def deleteNode(self, target):
    del target

 

노드 삽입

appendNode 함수입니다.

이 함수도 싱글 링크드 리스트와 마찬가지로 헤드가 있을 때와 없을 때로 나누어서 만들어야 합니다.

 

① 헤드가 없는 경우

     현재 데이터가 없기 때문에 새 노드를 헤드 자리에 바로 넣습니다.

② 헤드가 있는 경우

     새로 추가되는 노드(NewNode)를 테일로 설정하고 앞 노드로 원래의 테일 노드를 넣습니다. 그리고 원래의 테일 노드의 다음 노드에 새 노드를 설정합니다.

그리고 테일이 없는 경우에는 테일에 바로 넣고 헤드의 다음 노드로 설정하며 테일의 이전 노드로 헤드를 설정합니다.

 

사이즈(size)를 1 올리는 것도 잊으면 안됩니다.

def appendNode(self, NewNode):
    if self.head.data == None: # 헤드가 없는 경우
        self.head = NewNode # 헤드에 새 노드를 저장한다.
        self.tail = None
            
    else: # 헤드가 있는 경우
        if self.tail == None:
            self.tail = NewNode
            self.head.next = self.tail
            self.tail.prev = self.head
        else:
            NewNode.prev = self.tail
            self.tail.next = NewNode
            self.tail = NewNode

    self.size += 1

다음은 insertAfter 함수입니다.

이 함수는 싱글 링크드 리스트와 마찬가지로 특정 인덱스 뒤에 노드를 삽입합니다.

def insertAfter(self, location, NewNode):
    current = self.getNodeByLocation(location)
    NewNode.next = current.next
    NewNode.prev = current

    if current.next != None:
        current.next.prev = NewNode
        current.next = NewNode

    self.size += 1

 

기본적으로는 싱글 링크드 리스트와 같지만 다음 노드와 이전 노드를 생각해야합니다.

새 노드가 특정 노드(current) 뒤에 삽입되는 것이기 때문에 새 노드의 다음 노드에 current의 다음 노드를 넣고

새 노드의 이전 노드에 current를 넣습니다.

 

그 뒤에 새 노드를 current 뒤에 넣습니다.

 

노드 삭제

이번엔 노드를 삭제하는 함수 removeNode 함수입니다.

노드를 삭제할 때에도 다음 노드에 대한 포인터와 이전 노드에 대한 포인터를 생각해주어야 합니다.

그래서 지우는 노드(target)의 다음 노드와 이전 노드를 None으로 없애서 포인터를 끊습니다.

또한 타겟의 다음 노드, 이전 노드가 리스트에서 없어지지 않도록 그 다음 노드, 그 이전의 노드와 연결해줍니다.

def removeNode(self, target):
    if self.head == target: # 헤드가 타겟(지우고자 하는 노드)라면
        self.head = target.next # 헤드의 다음 노드를 헤드로 설정한다.
        if self.head != None: # 이 노드가 None이 아니면
            self.head.prev = None # 이 노드의 이전 노드를 설정하지 않는다.
        
        target.prev = None # 타겟(지워지는 노드)의 이전 노드, 다음 노드 포인터를 없앤다.
        target.next = None
    else:
        temp = target # 타겟 정보를 임시 저장합니다.

        if target.prev != None: # None이 아닌 경우
            target.prev.next = temp.next # 지우는 타겟의 다음 노드를 타겟의 이전 노드의 다음 노드 포인터로 지정합니다.
            
        if target.next != None:
            target.next.prev = temp.prev # 지우는 타겟의 이전 노드를 타겟의 다음 노드의 이전 노드 포인터로 지정합니다.
            
        target.prev = None
        target.next = None

    self.size -= 1 # 사이즈를 1 뺀다
    self.deleteNode(target)

노드 탐색

이제 노드를 탐색해봅시다.

이건 싱글 링크드 리스트와 같습니다.

def getNodeByLocation(self, location):
    current = self.head

    if location >= self.size:
        print('location Error')
        return None
        
    if location == 0:
        return current
    else:
        for i in range(location):
            current = current.next
        return current

노드 출력

노드를 출력하는 PrintNode 함수를 클래스 밖에 만들었습니다.

def PrintNode(node):
    if node.prev == None:
        print("Prev: NULL | ", end="")
    else:
        print(f'Prev: {node.prev.data} | ', end="")
        
    print(f'Current: {node.data} | ', end="")

    if node.next == None:
        print("Next: NULL")
    else:
        print(f'Next: {node.next.data}')

이제 마지막으로 메인 부분까지 구현해 봅시다.

 

메인

DLL = DoublyLinkedList() # 객체 생성

# 노드 생성 및 추가
for i in range(3):
    NewNode = DLL.createNode(i+1)
    DLL.appendNode(NewNode)

# 더블 링크드 리스트 출력
print('---------------------------------')
size = DLL.getSize()
print(size)
for i in range(size):
    current = DLL.getNodeByLocation(i)
    PrintNode(current)

# 노드 제거
current = DLL.getNodeByLocation(1)
DLL.removeNode(current)

# 출력
print('---------------------------------')
size = DLL.getSize()
print(size)
for i in range(size):
    current = DLL.getNodeByLocation(i)
    PrintNode(current)

# 노드 추가
NewNode = DLL.createNode("NewNode")
DLL.insertAfter(0, NewNode)

# 출력
print('---------------------------------')
size = DLL.getSize()
print(size)
for i in range(size):
    current = DLL.getNodeByLocation(i)
    PrintNode(current)

정리

 

그럼 이제 마지막 정리를 해볼까요?

더블 링크드 리스트는 싱글 링크드 리스트와 달리 양쪽으로 연결되어 있는 리스트입니다.

그렇기 때문에 다음 노드에 대한 포인터 뿐만이 아니라 이전 노드에 대한 포인터까지 생각해야합니다.

그래서 처음 구현하기는 까다롭고 복잡한 경향이 있으나, 노드가 많은 경우에 반대쪽에서 탐색할 수도 있기 때문에 용이하기도 합니다.

---

아래는 전체 파일입니다.

DLL.py

0.00MB

감사합니다.