[Python] 이중 연결리스트 구현

이중 연결리스트는 단순 연결리스트와 다르게 앞뒤 노드, 양쪽 방향으로 링크를 갖는 구조이다

단순 연결리스트의 구조를 이해하고 있으면 이중 연결리스트는 쉽게 이해할 수 있다결리스트는 단순 연결리스트와 다르게 앞뒤 노드, 양쪽 방향으로 링크를 갖는 구조이다

 

단순 연결리스트의 구조를 이해하고 있으면 이중 연결리스트는 쉽게 이해할 수 있다

01

단순 연결리스트와 이중 연결리스트

이중 연결리스트는 단순 연결리스트와 다르게 이전 노드에 접근이 가능하다는 장점이 있다

이전 노드에 접근할 수 있다는 말은 특정 노드 이전의 값을 삭제하거나 역으로 출력하는 등 추가적인 연산이 가능하다

 

구현하려는 이중 연결리스트의 추상 데이터 타입은 다음과 같다

• empty(): 리스트가 비었다면 True, 아닐 경우 False를 반환
• append(data): 리스트의 맨 뒤에 data를 추가
• appendleft(data): 리스트의 처음에 data를 추가
• insert_before(next_data, new_data): next_data 앞에 new_data를 추가
• insert_after(prev_data, new_data): prev_data 뒤에 new_data를 추가
• pop(): 리스트의 맨 뒤의 data를 반환, 반환할 값이 없는 경우 IndexError 발생
• popleft(): 리스트의 맨 처음 data를 반환, 반환할 값이 없는 경우 IndexError 발생
• __str__(): 출력 함수
• __len__(): 크기 반환 함수

---

1. 노드

단순 연결리스트와 마찬가지로 이중 연결리스트를 구현하기에 앞서 노드를 구현해보자

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

노드는 이전 값을 나타내는 prev와 다음 값을 나타내는 next를 갖는다

 

2. 연결리스트

class DoubleLinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = self.head

이중 연결리스트는 연결리스트의 시작을 나타내는 head와 끝을 나타내는 tail을 갖는다

head는 리스트의 첫 번째 원소를, tail은 리스트의 마지막 원소를 나타낸다

 

1) empty()

def empty(self):
    return not bool(self.head)

head가 None이 아닌 값을 갖는 경우 False를, None을 갖는 경우 True를 반환한다

 

2) append(data)

def append(self, data):
    if self.head is None:
        self.head = Node(data)
        self.tail = self.head
    else:
        node = self.tail
        new_node = Node(data, prev=node)
        node.next = new_node
        self.tail = new_node

head에 노드가 없는 경우 새로운 노드를 만들고 만들어진 노드가 리스트의 head가 된다

이미 head가 있는 경우 리스트의 마지막에 값을 추가한다

기존 리스트의 마지막 값(self.tail)의 next가 new_node를 가리키게 하고 new_node의 prev가 기존 리스트의 마지막 값을 가리키도록 한다

 

3) appendleft(data)

def appendleft(self, data):
    if self.head is None:
        self.head = Node(data)
        self.tail = self.head
    else:
        node = self.head
        new_node = Node(data, next=node)
        node.prev = new_node
        self.head = new_node

head에 노드가 없는 경우 새로운 노드를 만들고 만들어진 노드가 리스트의 head가 된다

이미 head가 있는 경우 리스트의 처음에 값을 추가한다

기존 head의 prev가 new_node를 가리키게 하고 new_node의 next가 기존 리스트의 첫 번째 값을 가리키게 한다

 

4) insert_before(next_data, new_data)

def insert_before(self, next_data, new_data):
    if self.head is None:
        self.head = Node(new_data)
        self.tail = self.head
    else:
        node = self.tail
        while node.data != next_data:
            node = node.prev
            if node is None:
                return False
        prev_node = node.prev
        new_node = Node(new_data, prev=prev_node, next=node)
        if prev_node:
            prev_node.next = new_node
        else:
            self.head = new_node
        node.prev = new_node
        return True

- 이중 연결리스트를 사용하면 이전 노드의 값을 참조할 수 있기 때문에 특정 노드 이전에 노드를 추가할 수 있다

- 단순 연결리스트를 사용해도 다음 노드가 가리키는 값을 먼저 참조해 특정 노드 이전에 노드를 추가할 수 있지만 이중 연결리스트를 사용하면 훨씬 자연스럽게 구현할 수 있다

- 위에 append, appendleft 메소드처럼 head가 없는 경우 새로 삽입하는 노드가 리스트의 head가 된다

- 리스트를 역으로 순회하며 찾으려는 값(next_data)을 찾고, next_data를 찾았다면 next_data를 포함한 노드의 prev가 새로운 값을 포함하는 노드(new_node)를 가리키도록하고 new_node의 next가 next_data를 포함한 노드(next_node)를 가리키도록 한다

 

5) insert_after(prev_data, new_data)

def insert_after(self, prev_data, new_data):
    if self.head is None:
        self.head = Node(new_data)
        self.tail = self.head
    else:
        node = self.head
        while node.data != prev_data:
            node = node.next
            if node is None:
                return False
        next_node = node.next
        new_node = Node(new_data, prev=node, next=next_node)
        if next_node:
            next_node.prev = node
        else:
            self.tail = new_node
        node.next = new_node

- head가 없는 경우 새로 삽입하는 노드가 리스트의 head가 된다

- head에서부터 리스트를 순회하면서 before_data를 찾는다면 다음 노드에 새로운 데이터를 추가한다

- prev_data를 찾았다면 prev_data를 포함한 노드의 next가 새로운 노드(new_node)를 가리키도록하고 new_node의 prev가 prev_data를 포함한 노드(prev_node)를 가리키도록 한다

 

6) pop()

def pop(self):
    if self.head is None:
        raise IndexError('LinkedList is empty')
    item = self.tail.data
    self.tail = self.tail.prev
    self.tail.next = None
    return item

리스트의 마지막 값을 반환한다, 리스트가 비었을 경우 IndexError를 일으킨다

 

7) popleft()

def popleft(self):
    if self.head is None:
        raise IndexError('LinkedList is empty')
    item = self.head.data
    self.head = self.head.next
    self.head.prev = None
    return item

리스트의 첫번째 값을 반환한다, 리스트가 비었을 경우 IndexError를 일으킨다

 

8) __str__()

def __str__(self):
    node = self.head
    result = ""
    while node is not None:
        result = result + str(node.data) + " "
        node = node.next
    return result

출력함수로 리스트의 저장된 값을 string으로 받아 result에 저장한다

string 타입인 result를 반환한다 

 

9) __len__()

def __len__(self):
    node = self.head
    cnt = 0
    while node is not None:
        cnt += 1
        node = node.next
    return cnt

리스트의 길이를 반환하는 함수로, 리스트를 순환하면서 노드 당 cnt값을 하나씩 증가시키고 cnt값을 반환한다

 

3. 예제코드

if __name__ == '__main__':
    DL = DoubleLinkedList()
    DL.append(1); DL.append(3); DL.append(5); print(DL)
    DL.appendleft(100); print(DL)
    DL.insert_after(1, 2); print(DL)
    DL.insert_before(5, 4); print(DL); print(len(DL))
    DL.pop(); print(DL)
    DL.popleft(); print(DL)
    print(len(DL))

1 3 5
100 1 3 5
100 1 2 3 5
100 1 2 3 4 5
6
100 1 2 3 4
1 2 3 4
4

 

4. 전체코드

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


class DoubleLinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = self.head

    def empty(self):
        return not bool(self.head)

    def append(self, data):
        if self.head is None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.tail
            new_node = Node(data, prev=node)
            node.next = new_node
            self.tail = new_node

    def appendleft(self, data):
        if self.head is None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            new_node = Node(data, next=node)
            node.prev = new_node
            self.head = new_node

    def insert_before(self, next_data, new_data):
        if self.head is None:
            self.head = Node(new_data)
            self.tail = self.head
        else:
            node = self.tail
            while node.data != next_data:
                node = node.prev
                if node is None:
                    return False
            prev_node = node.prev
            new_node = Node(new_data, prev=prev_node, next=node)
            if prev_node:
                prev_node.next = new_node
            else:
                self.head = new_node
            node.prev = new_node
            return True

    def insert_after(self, prev_data, new_data):
        if self.head is None:
            self.head = Node(new_data)
            self.tail = self.head
        else:
            node = self.head
            while node.data != prev_data:
                node = node.next
                if node is None:
                    return False
            next_node = node.next
            new_node = Node(new_data, prev=node, next=next_node)
            if next_node:
                next_node.prev = node
            else:
                self.tail = new_node
            node.next = new_node

    def pop(self):
        if self.head is None:
            raise IndexError('LinkedList is empty')
        item = self.tail.data
        self.tail = self.tail.prev
        self.tail.next = None
        return item

    def popleft(self):
        if self.head is None:
            raise IndexError('LinkedList is empty')
        item = self.head.data
        self.head = self.head.next
        self.head.prev = None
        return item

    def __str__(self):
        node = self.head
        result = ""
        while node is not None:
            result = result + str(node.data) + " "
            node = node.next
        return result

    def __len__(self):
        node = self.head
        cnt = 0
        while node is not None:
            cnt += 1
            node = node.next
        return cnt


if __name__ == '__main__':
    DL = DoubleLinkedList()
    DL.append(1); DL.append(3); DL.append(5); print(DL)
    DL.appendleft(100); print(DL)
    DL.insert_after(1, 2); print(DL)
    DL.insert_before(5, 4); print(DL); print(len(DL))
    DL.pop(); print(DL)
    DL.popleft(); print(DL)
    print(len(DL))