링크드 리스트

1. 링크드 리스트 개념

연결 리스트(Linked list)

• 하나의 노드에 데이터를 저장하고 각 노드들을 순서대로 연결시켜서 만든 자료 구조
• 노드 객체에는 data, next(다음 노드에 대한 레퍼런스) 두 가지 속성이 있다.

2. 링크드 리스트 만들기

class Node:
    """링크드 리스트의 노드 클래스"""

    def __init__(self, data):
        self.data = data  # 노드가 저장하는 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스


class LinkedList:
    """링크드 리스트 클래스"""

    def __init__(self):
        self.head = None
        self.tail = None

    def pop_left(self):
        """링크드 리스트의 가장 앞 노드 삭제 메소드. 단, 링크드 리스트에 항상 노드가 있다고 가정한다"""
        data = self.head.data

        if self.head is self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next

        return data

    def delete_after(self, previous_node):
        """링크드 리스트 삭제 연산. 주어진 노드 뒤 노드를 삭제한다"""
        data = previous_node.next.data

        if previous_node.next is self.tail:
            previous_node.next = None
            self.tail = previous_node
        else:
            previous_node.next = previous_node.next.next

        return data

    def prepend(self, data):
        """링크드 리스트의 가장 앞에 데이터 삽입"""
        new_node = Node(data)

        if self.head is None:
            self.tail = new_node
        else:
            new_node.next = self.head

        self.head = new_node

    def insert_after(self, previous_node, data):
        """링크드 리스트 주어진 노드 뒤 삽입 연산 메소드"""
        new_node = Node(data)

        if previous_node is self.tail:
            self.tail.next = new_node
            self.tail = new_node
        else:
            new_node.next = previous_node.next
            previous_node.next = new_node

    def find_node_at(self, index):
        """링크드 리스트 접근 연산 메소드. 파라미터 인덱스는 항상 있다고 가정"""
        iterator = self.head

        for _ in range(index):
            iterator = iterator.next

        return iterator

    def find_node_with_data(self, data):
        """링크드 리스트에서 탐색 연산 메소드. 단, 해당 노드가 없으면 None을 리턴한다"""
        iterator = self.head

        while iterator is not None:
            if iterator.data == data:
                return iterator
            iterator = iterator.next

        return None

    def append(self, data):
        """링크드 리스트 추가 연산 메소드"""
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def __str__(self):
        """링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
        res_str = "|"

        iterator = self.head

        while iterator is not None:
            res_str += f" {iterator.data} |"
            iterator = iterator.next

        return res_str


# 새로운 링크드 리스트 생성
my_list = LinkedList()

# 링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)
my_list.append(11)

# 링크드 리스트 노드에 접근 (데이터 가지고 오기)
print(my_list.find_node_at(3).data)

# 링크드 리스트 노드에 접근 (데이터 바꾸기)
my_list.find_node_at(2).data = 13

# 링크드 리스트 __str__ 호출
print(my_list)

7
| 2 | 3 | 13 | 7 | 11 |

3. 링크드 리스트 시간 복잡도

접근

• Worst-case time complexity: O(n)
• Best-case time complexity: O(1)
• Average time complexity: O(n)

탐색

• Worst-case time complexity: O(n)
• Best-case time complexity: O(1)
• Average time complexity: O(n)

삽입/삭제

• Worst-case time complexity: O(1)
• Best-case time complexity: O(1)
• Average time complexity: O(1)

현실적인 삽입/삭제 시간 복잡도

• previous_node를 먼저 찾은 후 삽입/삭제를 해야 하기 때문에 결론적으로 총 O(n)의 시간 복잡도를 갖게 된다.
• Head node에 접근해서 삽입/삭제하거나 Tail node에 접근해서 삽입하는 시간 복잡도는 O(1)이다.

4. 더블리 링크드 리스트

더블리 링크드 리스트(Doubly linked list)

• next node에 대한 레퍼런스뿐만 아니라 previous node에 대한 레퍼런스도 가지고 있는 링크드 리스트
• 위에 작성했던 next node에 대한 레퍼런스만 가지고 있는 링크드 리스트를 싱글리 링크드 리스트(Singly Linked List)라고 한다.

5. 더블리 링크드 리스트 만들기

class Node:
    """더블리 링크드 리스트의 노드 클래스"""

    def __init__(self, data):
        self.data = data  # 노드가 저장하는 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스
        self.prev = None  # 이전 노드에 대한 레퍼런스


class LinkedList:
    """더블리 링크드 리스트 클래스"""

    def __init__(self):
        self.head = None
        self.tail = None

    def delete(self, node_to_delete):
        """더블리 링크드 리스트 삭제 연산 메소드"""
        data = node_to_delete.data

        if node_to_delete is self.head and node_to_delete is self.tail:
            self.head = None
            self.tail = None
        elif node_to_delete is self.head:
            self.head = node_to_delete.next
            self.head.prev = None
        elif node_to_delete == self.tail:
            self.tail = node_to_delete.prev
            self.tail.next = None
        else:
            node_to_delete.prev.next = node_to_delete.next
            node_to_delete.next.prev = node_to_delete.prev

        return data

    def prepend(self, data):
        """뎌블리 링크드 리스트의 가장 앞에 데이터 삽입"""
        new_node = Node(data)

        if self.head is None:
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node

        self.head = new_node

    def insert_after(self, previous_node, data):
        """더블리 링크드 리스트 추가 연산 메소드"""
        new_node = Node(data)

        if previous_node is self.tail:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        else:
            new_node.prev = previous_node
            new_node.next = previous_node.next
            new_node.next.prev = new_node
            previous_node.next = new_node

    def find_node_at(self, index):
        """링크드 리스트 접근 연산 메소드. 파라미터 인덱스는 항상 있다고 가정"""
        iterator = self.head

        for _ in range(index):
            iterator = iterator.next

        return iterator

    def find_node_with_data(self, data):
        """링크드 리스트에서 탐색 연산 메소드. 단, 해당 노드가 없으면 None을 리턴한다"""
        iterator = self.head

        while iterator is not None:
            if iterator.data == data:
                return iterator
            iterator = iterator.next

        return None

    def append(self, data):
        """더블리 링크드 리스트 추가 연산 메소드"""
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def __str__(self):
        """링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
        res_str = "|"

        iterator = self.head

        while iterator is not None:
            res_str += f" {iterator.data} |"
            iterator = iterator.next

        return res_str

6. 싱글리 vs 더블리 링크드 리스트

더블리 링크드 리스트의 시간 복잡도

• tail node에 접근해서 삭제하려고 할 때 O(1)인 점 빼고는 싱글리 링크드 리스트와 똑같다.

추가적 공간 복잡도

• 싱글리 링크드 리스트: O(n)
• 더블리 링크드 리스트: O(2n) = O(n)
• 복잡도는 같지만 실제로는 두 배 정도가 차이 나므로 공간을 효율적이게 쓰고 싶다면 싱글리 링크드 리스트를 활용해도 좋다.

Feedback

1. 다른 언어로 링크드 리스트를 구현해보자.
2. 링크드 리스트 라이브러리를 찾아보자.
3. Garbage collector의 원리를 공부해보자.

참고 자료

• 기본 자료 구조들 - 알고리즘 · 자료구조 강의 | 코드잇