<코딩테스트 Level1> 10일차 - 링크드 리스트

📌 링크드 리스트(Linked List)

링크드 리스트, 연결 리스트(Linked List)는 데이터와 포인터로 구성된 노드를 한 줄로 연결하여 데이터를 저장하는 자료구조이다.

링크드 리스트는 Head에서 시작하고, Head는 Node 1의 주소 값을 가지고 있다. 즉, Head를 사용해 Node 1에 접근할 수 있다.

그럼, Head를 통해 접근한 Node 1은 어떤 구조일까 ❓
위에서 언급했듯 노드는 데이터와 포인터로 이루어져있다.

데이터는 의미 그대로 그 노드에 저장할 데이터를 의미하고, 포인터는 다음 노드의 주소 값을 의미한다.

따라서 Head에서 Node 1에 접근했던 것과 마찬가지로 Node 1의 포인터로 Node2에 접근하고, Node 2의 포인터로 Node3에 접근할 수 있다.

이렇게 모든 데이토가 포인터로 연결되어 있는 특정 때문에 Linked List라는 이름이 붙었다.

📌 링크드 리스트의 장점 / 단점

❗ 장점과 단점들은 C언어의 기본 배열을 생각하라.
파이썬의 리스트 자료형은 링크드 리스트의 모든 기능을 지원한다.

📝 장점

• 링크드 리스트 크기를 미리 할당할 필요가 없다.
• 링크드 리스트 수정 시, 시간 복잡도가 O(1)이다.

📝 단점

• 추가적인 저장 공간이 필요하다.
• 정보를 가져오기 위한 시간 복잡도가 O(n)이다.

📌 링크드 리스트 구현

링크드 리스트는 일반적으로 아래와 같은 메소드들을 구현하고 사용한다.

• append(value) : 링크드 리스트의 마지막에 데이터를 추가
• insert(value, idx) : 링크드 리스트의 idx 위치에 데이터 추가
• delete(idx) : 링크드 리스트의 idx 위치 노드를 제거
• get(idx) : 링크드 리스트의 idx 위치의 노드를 가져온다.

# 노드 클래스.
# 생성자로 데이터와 포인터를 받는다.
# 포인터가 입력이 안된 경우, 해당 노드가 종단점이라는 의미.
class Node:
    def __init__(self, data, pointer=None):
        self.data = data
        self.pointer = pointer

# 링크드리스트 클래스.
# 클래스 객체 생성시 데이터가 존재하지 않는 노드를 생성한다.
# 해당 노드의 포인터가 바로 Head.
class LinkedList(object):
    def __init__(self):
        self.head = Node(None)
        # 링크드리스트의 노드 개수를 저장하는 변수 size.
        self.size = 0

    # idx 위치에 존재하는 노드를 받아온다.
    def get(self, idx):
        # 입력된 인덱스가 링크드리스트 사이즈보다 클 경우, 오류가 발생.
        if idx >= self.size:
            print("Index Error")
            return None
        # 인덱스가 0인 경우, 헤드를 받아오라는 의미
        if idx == 0:
            return self.head
        else:
            node = self.head
            for _ in range(idx):
                node = node.pointer
            return node

    # 데이터를 링크드리스트 종단점으로 추가한다.
    def append(self, data):
        if self.size == 0:
            self.head = Node(data)
            self.size += 1
        else:
            node = self.head
            # 종단점의 포인터는 None값을 가짐.
            while node.pointer != None:
                node = node.pointer

            new_node = Node(data)
            node.pointer = new_node
            self.size += 1

    # 데이터를 idx 위치에 추가한다.
    def insert(self, value, idx):
        if self.size == 0:
            self.head = Node(value)
            self.size += 1
        # idx가 0이라는건, Head 자리에 새로운 데이터를 넣는다는 의미.
        elif idx == 0:
            self.head = Node(value, self.head)
            self.size += 1
        else:
            node = self.get(idx - 1)
            if node == None:
                return

            new_node = Node(value)

            next_node = node.pointer
            # 삽입하려는 idx 이전의 노드의 포인터를 새로운 노드로 설정
            node.pointer = new_node
            # 현재 노드의 포인터를 삽입하려는 idx 이후의 노드로 설정
            new_node.pointer = next_node
            self.size += 1

    # idx 위치의 노드를 삭제한다.
    def delete(self, idx):
        if self.size == 0:
            print("Empty Linked List")
            return
        elif idx >= self.size:
            print("Index Error")
            return
        elif idx == 0:
            self.head = self.head.pointer
            self.size -= 1
        else:
            node = self.get(idx - 1)
            node.pointer = node.pointer.pointer
            self.size -= 1

    def print_linked_list(self):
        node = self.head
        while node:
            if node.pointer != None:
                print(node.data, "-> ", end="")
                node = node.pointer
            else:
                print(node.data)
                node = node.pointer

LL = LinkedList()
LL.append("Data1")
LL.print_linked_list()
LL.append("Data2")
LL.print_linked_list()
LL.append("Data3")
LL.print_linked_list()
LL.insert("Data4", 1)
LL.print_linked_list()

LL.delete(0)
LL.print_linked_list()
LL.delete(2)
LL.print_linked_list()
LL.delete(0)
LL.print_linked_list()

📌 정리

링크드 리스트도 스택과 큐처럼 단독으로는 잘 사용되지 않는다.

하지만 다른 자료구조와 결합되므로 그만큼 기본이 된다.