singly Linked List란?
singly Linked List는 node들을 연결시킨 자료구조이다.
각 node는 데이터(element)를 저장하는 데이터필드와 다음 노드를 가리키는 링크필드로 구성된다.
node는 서로 다른 데이터타입을 하나로 묶으므로 class에 해당된다.
따라서 링크필드에 해당하는 것은 class 포인터이다. (이를 노드형 포인터라고도 함)
Linked List의 첫 node를 head라 하고, 끝 node를 tail이라 한다. (tail의 경우 NULL값을 가리킨다.)
ex. class Node { int data; NODE* next; }
주요 method
addFront(element)
1. 새로운 노드 할당
2. 새로운 값 삽입
3. 새로운 노드가 이전 헤드를 가리키게 한다.
4. 새로 삽입된 노드를 head로 업데이트
O(1)의 시간복잡도를 갖는다.
removeFront()
1. 기존 head의 다음 노드를 head로 업데이트한다.
2. 기존 head를 De_allocate한다.
O(1)의 시간복잡도를 갖는다.
addTail(element)
1. 새로운 노드 할당
2. 값 삽입
3. 새 노드가 null을 가리키게 한다.
4. 기존 tail이 새로운 노드를 가리키게 한다.
5. 새로운 노드를 tail로 업데이트한다.
O(1)의 시간복잡도를 갖는다.
remoneTail()
1. 기존 tail의 이전 노드가 null을 가리키도록 수정
2. 이전노드를 새로운 테일로 지정
3. 기존 tail 삭제
tail을 삭제하려면 tail 이전 노드의 주소를 알기 위해 head에서부터 next를 반복해야 한다.
따라서 singly linked list에서 tail을 삭제하는건 매우 비효율적이다.
이와 같은 단점을 보완한 것이 바로 Doubly Linked List이다.
Doubly Linked List란?
이중연결리스트에서는 이전노드와 다음노드에 대한 주소값이 동시에 저장되어 있다.
주요 method
add(p, element) (p노드 앞에 e를 삽입하겠다.)
1. 새 노드 "v" 생성
2. 새로운 값 삽입
3. v->next = p; p->prev = v (v와 p를 연결)
4. v->prev = u; u->next = v (v와 u를 연결)
O(1)의 시간복잡도를 갖는다.
remove(p)
u = p -> prev
w = p -> next (포인터를 이용하여 원래 연결 알아내기)
u -> next = w (lingking out p)
w -> prev = u
O(1)의 시간복잡도를 갖는다.
