Linked List

기본 개념

최소 단위인 Node의 경우 value와 nextnode를 갖으며 아래 코드가 기본적인 Node 코드이다.

class Node():
    def __init__(self, value):
    	self.value = value
        self.nextnode = None

Linked list의 경우 이러한 node가 여러개 연결되어 있으며 first node -> head, last node ->tail 이라 부른다. 또한 tail의 경우에는 tail.nextnode가 None이 된다.

traversing

Linked list에서의 핵심 키워드 중 하나는 traversing이다. 어떤 값을 찾는 데에 있어 Head부터 Tail까지 node를 각각 방문해 가며 찾는 것을 traversing이라 하며, 이 때 현재 확인하고 있는 node를 가리켜 'pointer'라고 한다.

insert

아래와 같은 sequence를 따른다.
1. input value에 맞춰 new node를 만든다.
2. new node의 nextnode를 현재 Headnode로 설정한다.
3. Head를 new node로 재할당해준다.

remove

1. Head node의 nextnode를 None으로 바꿔준다. (link 끊기)
2. 두번째 node를 Head node로 지정해준다.

linked list의 경우 Head부터 순차적으로 탐색이 가능하므로 tail 쪽에서의 insert나 remove는 어렵다.

주요 특징

pros

• insert와 delete method 모두 constant time으로 시행 가능하다. (Array의 경우 O(n) time이 걸린다.)
• Node를 이어 붙이고 제거하는 형태이므로 size의 제한을 받지 않고 지속적으로 확장이 가능하다.

cons

• Linked list안에 있는 값에 접근하는 것이 어렵다. k번째에 존재하는 value에 접근하기 위해선 O(k) time이 걸리게 된다. (Array의 경우 O(1))

linked list cycle에서 two pointer runner idea!

Doubly linked list

기본개념

Doubly Linked List라고 해서 크게 달라지는 것은 없다. 다만 Linked List에 존재하던 여러 단점을 극복할 수 있게된다.
기본 단위 Node는 살짝 수정된다.

class DoublyNode():

    def __init__(self, value):
    	self.value = value
        self.nextnode = None
        self.prevnode = None

이런 식으로 기존 node에서는 value와 nextnode만 존재했다면 DLL에서는 prevnode라는 것이 존재하게 된다.

주요 특징

Pros

• 기존의 Linked List에서는 Head에서만 insert/remove가 가능했지만, 이제는 각 node가 자신의 이전과 이후를 알고 있으므로 Head와 Tail 에서 모두 insert/remove가 가능하다.
• 또 위와 같은 이유로 양방향 탐색이 가능하다.

Cons

• Node가 데이터를 하나 더 저장해야 하므로 메모리 사용이 증가한다.(그러나 장점이 더 커서 현실에서는 대부분 DLL을 쓴다.)
• 기존에 존재하던 탐색에 대한 time complexity는 반으로 줄었긴 하나, 여전히 array보다는 많이 뒤처진다.