Linked List

Linked list는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.

• 노드(node): 데이터를 담고 있는 그릇. 주로 class로 구현되므로 class라고 생각해도 관계 없다.
• 링크(link): 리스트의 순서를 유지할 수 있게 해주는 연결고리.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None

class LinkedList:
    def __init__(self):
        self.headval = None

list1 = LinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

Doubly Linked List

Doubly Linked List는 다음 노드 뿐만이 아니라 전 노드의 링크도 가지고 있는 Linked list다. 즉, 리스트의 앞과 뒤 양방향으로 이동이 가능한 리스트이다.

Circular Linked List

Circular Linked List의 tail부분이 head부분과 연결된 Linked list다.그러므로 리스트의 무한 반복이 가능하다.

Array와 차이점

Array와 비슷하게 순차열적으로 요소들을 저장하지만 근본적으로 많은 차이가 있다.

Array는 데이터를 논리적 순서에 따라 순차적으로 입력하며, 물리적 주소 또한 순차적이다. Linked list는 데이터를 논리적 순서에 따라 데이터를 입력하지만 물리적 주소는 순차적이지 않다는 것이 다르다.

배열은 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능(indexing)하기 때문에 데이터 접근 속도가 매우 빠르다. 인덱스를 가지고 있는 배열과는 달리 연결리스트는 인덱스 대신 현재 위치의 이전 및 다음 위치만을 알고 있다. 그러므로 한번에 데이터 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능하므로 배열에 비해 원하는 데이터에 접근하는 속도가 떨어진다.

배열은 데이터의 삽입이나 삭제에 취약하다. 배열 특성상 데이터 삽입이나 삭제가 이루어지면 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 하기 때문이다. 그에 반해 Linked list에서의 데이터 삽입이나 삭제는 논리적 주소만 바꿔주면 되기 때문에 훨씬 쉽고 간편하다.

또한 일한 양의 데이터를 저장해도 일반적으로 Linked list가 배열보다 더 많은 메모리를 차지하게 된다. 배열은 단순 데이터 저장인데 비해 Linked list는 각 노드마다 객체를 생성해야 하기 때문이다.

When To Use Linked List

데이터 양이 많지만 데이터의 삽입이나 삭제가 거의 없고, 데이터에 대한 접근이 빈번하게 이루어질 경우는 배열을 사용하는 것이 유리하다.
그러나 데이터 양이 그렇게 많지 않고, 데이터의 삽입이나 삭제가 빈번하게 이루어질 경우에는 Linked list를 사용하는 것이 더 유리하다.