[자료구조] Linked List(링크드 리스트)

Linked List(링크드 리스트)란?

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

Node에는 데이터(Node에 저장할 데이터)와, 포인터(다음 Node를 가리키는 주소 값)을 저장하고 있다. 

Head를 통해 첫 번째 Node에 접근할 수 있다.

포인터에 값이 없을 경우에는 종단점을 의미한다.

 

Linked List의 장단점

1) 장점

- Linked List의 크기를 미리 할당할 필요가 없다.

- Linked List를 수정 시, 시간 복잡도가 O(1)이다.

2) 단점
- 추가적인 저장공간이 필요하다.

- 정보를 가져오기 위한 시간복잡도가 O(n)이다.

※ C언어 장단점 (Python의 리스트 지료형은 Linked List의 모든 기능을 지원함)

 

Linked List의 삽입 구현하기

1. 삽입할 새로운 노드를 생성한다. (new_node)

2-1. 맨 앞에 새로운 노드를 삽입할 경우, Head는 새로운 노드를 가리키고, 새로운 노드의 포인터는 Head가 가지고 있던 포인터 값을 저장한다.

2-2. 연결된 Linked List의 중간에 새로운 노드를 삽입할 경우, 삽입할 위치의 앞 노드는 새로 생성한 노드를 가리키게 한하고, 새로 생성한 노드의 포인터는 삽입할 위치의 앞 노드기 가지고 있던 포인터 값을 저장한다.

 

Linked List 삭제 구현하기

1. 삭제할 노드를 찾는다.

2-1. 맨 앞에 노드(Head)를 삭제할 경우, Head는 삭제할 이후의 노드로 지정한다.

2-2 연결된 Linked List의 중간에 삭제할 노드가 있는 경우, 삭제할 노드의 앞의 노드는 삭제할 노드가 가리키는 포인터를 가리키게 한다.

3. 삭제할 노드를 삭제한다.

 

Linked List의 Node 구현하기

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

노드의 생성자로 데이터(data)와 포인터(next) 를 저장한다.

데이터는 Node에 저장될 Data, 포인터는 Node가 가리키는 정보이다.
pointer 변수에 값이 None인 경우, 해당 노드가 종단점이라는 뜻이다.

 

Linked List 구현하기

class LinkedList(object):
    def __init__(self):
        self.head = Node(None)
        self.size = 0

    def get(self, idx): # idx 위치에 존재하는 노드를 받아온다.
        if idx >= self.size:
            print("Index Error")
            return None
        if idx == 0:
            return self.head
        else:
            node = self.head
            for _ in range(idx):
                node = node.next
            return node

    def append(self, data): # 데이터를 Linked List 종단점으로 추가한다.
        if self.size == 0:
            self.head = Node(data)
            self.size += 1
        else:
            node = self.head
            while node.next != None:
                node = node.next

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

    def insert(self, value, idx): # 데이터를 idx 위치에 추가한다.
        if self.size == 0:
            self.head = Node(value)
            self.size += 1
        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.next
            node.next = new_node
            new_node.next = next_node
            self.size += 1

    def delete(self, idx): # 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.next
            self.size -= 1
        else:
            node = self.get(idx - 1)
            node.next = node.next.pointer
            self.size -= 1

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

 

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

print_linked_list(): 링크드 리스트로 연결된 데이터를 Head부터 끝까지 출력한다.