링크드 리스트(Linked List)

링크드 리스트(Linked List)

이름 그대로 "연결된 리스트".

C에서는 이 링크드 리스트가 주요한 데이터 구조라고 한다.(나의 C언어 학습은 15년 전 for문에서 멈춰있다...)

 

링크드 리스트의 기본 구조는 크게 두 가지.

Node(Nodejs 아님)와 Pointer.

Node는 링크드 리스트의 각 구성단위(데이터 값과 포인터를 가지는)이라고 할 수 있으며, 바로 앞에 괄호에서 말한 포인터라는 것은 각 노드가 다음 요소를 가리키는(point) 것을 말한다.

Linked List 예시(iPad로 직접 그림)

링크드 리스트에는 반드시 머리와 꼬리가 있으며, 이 머리와 꼬리를 포함한 모든 요소 하나하나가 노드(Node)인 것이다.

Linked List

class LinkedList:
    def __init__(self, head=None, tail=None):
        self.head=head
        self.tail=tail

Linked List의 기본 구조는 위와 같다. 머리가 있고, 꼬리가 있다. 이 머리와 꼬리를 포함, 몸통도 모두 아래의 Node로 구성된다.

 

Node

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

기본적인 노드 클래스 선언이다.

인스턴스 선언시에 data값을 포함해서 선언해 주는 것이다. 기본적으로 next는 일단 없는 것으로 가정한다.

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)

위에 그린 (못그린)그림에서와 같이 이렇게 6개의 노드 인스턴스를 선언한다고 가정하자.

Node클래스의 괄호 안에 있는 1에서 6까지의 수가 data값을 넣은 것이다.

위의 node1~node6의 인스턴스 모두 data값으로 각자의 숫자를 가지고 있고, 모두 next가 지정되지 않았다.

이 경우 위의 그림과 같이 만들려면 이렇게 해야 한다.

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6

node1에서 node5까지에 각자 next로 node2에서 node6까지를 지정하는 것이다.

print(node1.next == node2)
print(node2.next == node3)
print(node3.next == node4)
print(node4.next == node5)
print(node5.next == node6)

True
True
True
True
True

모두 올바르게 지정되었다는 것을 확인할 수 있다.

LinkedList에 데이터 지정하기

linked_list = LinkedList()
linked_list.head = node1
linked_list.tail = node6

or

linked_list = LinkedList(head=node1, tail=node6)

LinkedList 클래스의 init 메서드에서 head, tail 순으로 작성했으므로 head=와 tail=없이 해도 괜찮다.

linked_list = LinkedList(node1, node6)

내용을 살펴보면 아래와 같다.

print(linked_list.head == node1) # head는 node1이다.
print(linked_list.head.data) # head(node1)의 데이터는 1이다.
print(linked_list.head.next.data) # head의 다음의 데이터는 2다.

출력 결과

True
1
2

메서드를 추가한 Linked List 선언

class LinkedList:
    def __init__(self, head=None, tail=None):
        self.head=head
        self.tail=tail
        
    def add(self, data):
        node = Node(data) # 새 Node Instance 생성
        if self.head is None: # 아직 head가 없을 시 == 빈 LinkedList일 시
            self.tail = node # 꼬리로 node지정
            self.head = node # 머리도 node 지정
            self.head.next = self.tail # 머리의 다음으로 꼬리를 지정      
        else: # 빈 리스트가 아닐 시
            self.tail.next = node # 꼬리의 다음 것으로 새로 생성한 node 지정
            self.tail = node # 꼬리를 node로 변경

    def desc(self): # LinkedList의 내용 설명
        node = self.head # 처음에 머리를 지정(None이라 할지라도 일단은.)
        while node is not None: # node가 None이 아니라면 출력한다 == 처음부터 None이라면 아무것도 안 나온다.
            print(node.data, end=' ') # node의 data값을 출력하고
            node = node.next # node의 다음을 타겟으로 변경한다.

뭔가 코멘트도 많아졌다.

add 메소드를 추가했는데, data값을 넣으면 알아서 Node instance를 추가해서 List의 일원(?)으로 받아들이도록 한 것이라고 보면 된다.

linked_list = LinkedList()
linked_list.add(1)
linked_list.add(2)
linked_list.desc()

새로 덮어써 정의한 LinkedList instance를 만들고 add 두 번을 통해 1,2를 각각 data로 집어넣고, desc 메서드를 실행해 본다.

1 2 

출력 결과는 위와 같다.

(왜 1과 2가 색이 다른지는 나도 모른다.)

print(linked_list.head)
print(linked_list.head.data == 1) # linked_list의 머리는 node1이다.
print(linked_list.head.next.data == 2) # linked_list의 머리의 다음은 linked_list의 꼬리이다.
print(linked_list.head.next.data == linked_list.tail.data) # linked_list의 머리의 다음은 node2다.
print(linked_list.tail.data == 2) # linked_list의 꼬리는 node2다.

<__main__.Node object at 0x7fd3c134b580>
True
True
True
True

링크드 리스트의 장단점

장점

미리 데이터 공간을 할당할 필요가 없다.

단점

연결을 하기 위해 데이터 공간이 별도로 필요하기 때문에 저장공간 효율이 썩 좋지는 못하다.

연결 정보를 찾아야 해서 접근 속도가 느리다.

중간 데이터를 추가하거나 삭제하게 된다면 각 데이터의 next 정보 등을 다시 할당해야 하는 수고가 필요하다.