Linked list(연결 리스트)

Linked list 

-linked list는 원소들이 메모리 여기저기 흩어져 있고, 각 원소들이 다음 원소를 가리키는 포인터를 가지는 방식으로 구현됨

-임의의 위치에 원소를 삽입, 삭제하는 것이 시간이 오래걸리는 문제를 해결하기 위해 사용

-linked list를 사용하면 특정위치에서의 삽입과 삭제를 상수시간에 할 수 있음

-linked list는 첫번째 node(Head)와 마지막 node(Tail)에 대해 포인터의 가짐

 

 

Node(노드) : 사각형으로 표현된 원소와 포인터의 집합들을 list의 Nod라고 부름

struct ListNode
{
	int element; //담고 있는 원소
    ListNode* prev, next; //이전 노드, 다음 노드의 포인터
}

Linked list의 종류

-양방향 연결 리스트(Doubly linked list) : 각 원소가 이전과 다음 원소에 대한 정보를 모두 가짐

-단방향 연결 리스트(Singly linked list) : 각 원소가 다음 원소를 가리키는 포인터만 가짐

 

Linked list의 장점

-삽입과 삭제가 상수 시간에 이루어짐(포인터만 변경하면 되기 때문에)

 

Linked list의 단점

-Linked list는 메모리 여기저기에 Node들이 흩어져 있음

-따라서, 탐색의 경우 list의 머리에서 부터 시작해 하나씩 포인터를 따라가며 다음 Node를 찾을 수 밖에 없음

-걸리는 시간은 O(N) - list 길이에 선형 비례

 

삭제했던 Node 돌려놓기

-Doubly linked list의 장점

-삭제된 Node의 포인터들은 원래 자기가 들어가 있던 위치를 알고 있기 때문에 가능

-다만, 항상 삭제한 순서의 반대로 복구해야함(이전노드나 이후 노드 또한 삭제된 상태에서 수행하면 list를 망가뜨리기 때문)

 

*C++ STL의 list는 splice()멤버 함수를 통해 잘라 붙이기 연산을 지원하는 대신, list의 크기를 구하려면 O(N)의 반복문을 수행해야함 // 잘라 붙이기 연산을 할 때는 몇 개의 원소가 추가되는지 알 방법이 없기 때문에

반대로, Java,C#은 size()연산을 O(1)에 하는대신 잘라붙이기 연산 포기