linked lists는 객체들이 linear order로 배치되는 자료구조이다. 그러나, linear order가 배열의 인덱스들에 의해 결정되는 배열과 다르게, 링크드 리스트에서의 순서는 각 오브젝트에 있는 포인터에 의해 결정된다. Linked list는 동적 집합에 대해 간단하고 유연한 표기법을 제공한다. 그리고 그것은 (필수적으로 효율적이지 않을지라도) page 230에서 기재된 모든 연산을 지원한다.
그림 10.3에 보여지듯이 doubly linked list L의 각 요소는 key와 두 개의 다른 포인터 attributes를 (next and prev) 가진 오브젝트이다. 그 오브젝트는 또한 다른 satellite data를 포함할지도 모른다. 목록에 있는 요소 x가 주어진다면, x.next는 링크드 리스트에서 그것의 후계자를 가리키고, x.prev는 그것의 전임자를 가리킨다. 만약 x.prev == NIL이라면, 그 원소 x는 predecessor가 없고 그러므로, 그 list의 첫 번째 요소 또는 head이다. 한 속성 L.head는 그 리스트의 첫 번째 요소를 가리킨다. 만약 L.head == NIL이라면, 그 list는 비어있다.
한 list는 여러가지 형태 중의 하나를 가질지도 모른다. 그것은 singly(홀로) 연결되거나 또는 doubly(양쪽으로) 연결될지도 모르고, 그것은 정렬될 수도 있고, 그것은 circular할수도 있다. 만약 한 리스트가 singly linked라면, 우리는 각 요소에서 prev pointer를 생략한다. 만약 한 list가 sorted라면, 그 list의 linear order는 그 list의 원소에서 저장된 key들의 linear order와 일치한다.; 그 말은, 최소값의 element가 그 리스트의 head이고, 최대값의 element가 tail이다. 만약 그 list가 unsorted라면, 그 원소들은 어떤 순서로든 나타날 수 있다. circular list에서, 그 list의 head의 prev pointer는 tail을 가리키고 있고, 그 list의 tail의 next pointer는 head를 가리키고 있다. 우리는 circular list를 원소들의 고리로 생각할 수 있다. 이 섹션의 나머지에서, 우리는 우리가 작업하고 있는 lists들이 unsorted이고 doubly linked라고 가정한다.
Searching a linked list
LIST-SEARCH(L, k) procedure는 간단한 linear search로 list L에서 key가 k인 첫 번째 요소를 찾는다. 이것은 이 요소에 대한 포인터를 반환한다. 만약 key k를 가진 오브젝트가 그 리스트에서 나타나지 않는다면, 그러면 그 프로시져는 NIL를 반환한다. 그림 10.3(a)에서 링크드 리스트에 대해, LIST-SEARCH(L,4)은 세 번째 요소에 대한 포인터를 반환하고, LIST-SEARCH(L,7)에 대한 호출은 NIL을 반환한다.
LIST-SEARCH(L,k) 1 x = L.head 2 while x != NIL and x.key != k 3 x = x.next 4 return x
n개의 오브젝트들을 가진 한 list를 search하기 위해, LIST-SEARCH procedure는 최악의 경우에 theta(n) 시간이 걸린다. 그것이 전체 list를 search해야할지도 모르기 때문이다.
Inserting into a linked list
key attribute가 이미 설정된 element x가 주어진다면, LIST-INSERT procedure는 x를 링크드 리스트의 처음에 잇는다. 그림 10.3(b)에서 보여지듯이.
LIST-INSERT(L,k) 1 x.next = L.head 2 if L.head != NIL 3 L.head.prev = x 4 L.head = x 5 x.prev = NIL
(우리의 attribute notation이 cascade될 수 있다는 것을 상기하라. L.head.prev가 L.head가 가리키는 오브젝트의 prev 속성을 말한다.) n개의 요소를 가진 한 리스트에서 LIST-INSERT의 runnin tiime은O(1)이다.
Deleting from a linked list
LIST-DELETE 프로시저는 링크드 리스트 L에서 요소 x를 제거한다. 그것은 x에 대한 포인터가 주어져야만하고, 그러고나서 포인터를 업ㅂ데이트하여 그 리스트에서 x를 이어야 한다. 만약 우리가 주어진 key를 가진 element를 삭제하기를 원한다면, 우리는 그 element에 대한 포인터를 얻기 위해 처음에 LIST-SEARCH를 호출해야만 한다.
LIST-DELETE(L,k) 1 if x.prev != NIL 2 x.prev.next = x.next 3 else L.head = x.next 4 if x.next != NIL 5 x.next.prev = x.prev
그림 10.3(c)는 한 요소가 링크드 리스트에서 어떻게 삭제되는지를 보여준다. LIST-DELETE를 O(1)의 시간이 걸리지만, 만약 우리가 주어진 key를 가진 한 요소를 삭제하길 원한다면, theta(n) time이 최악의 경우에 요구된다.왜냐하면 우리는 처음에 그 요소를 찾기 위해 LIST-SEARCH를 호출해야만 하기 때문이다.
Sentinels
LIST-DELETE에 대한 코드는 만약 우리가 그 리스트의 head와 tail에서의 boundary conditions를 무시할수있다면 더 간단해진다:
LIST-DELETE(L,k) 1 x.prev.next = x.next 2 x.next.prev = x.prev
sentinel은 우리가 boundary conditions를 간단하게 해주는 dummy object이다. 예를들어, 우리가 NIL을 나타내지만 그 리스트에서 다른 오브젝트들의 모든 attributes들을 가진 한 오브젝트 L.nil을 list L과 함께 제공한다고 가정하자. 우리가 list code에서 NIL에 대한 참조를 어디에서 하든, 그것은 sentinel L.nil에 대한 참조를 바꿀 것이다. 그림 10.4에 보여지듯이, 이 변화는 보토의 doubly linked list를 circular, doubly linked list with a sentinel로 바꾼다. 그리고 거기에서, sentinel L.nil은 head와 tail사이에 놓여있다. L.nil.next attribute는 그 리스트의 head를 가리키고, L.nil.prev는 그 tail을 가리킨다. 유사하게, tail의 next attribute와 head의 prev는 L.nil을 가리킨다. L.nil.next는 head를 가리키기 때문에, 우리는 attribute L.head를 완전히 제거할 수 있고, 그것에 대한 참조를 L.nil.next에 대한 참조로 바꾼다. 그림 10.4(a)는 텅빈 list가 그냥 sentinel로 구성되어있는 것을 보여주고, L.nil.next와 L.nil.prev가 L.nil을 가리키는 것을 보여준다.
LIST-SEARCH에 대한 코드는 이전과 같게 남지만, NIL과 L,head에 대한 참조는 위에 명시한대로 변경된다:
LIST-SEARCH'(L,k) 1 x = L.nil.next 2 while x != L.nil and x.key != k 3 x = x.next 4 return x
우리는 리스트에서 한 원소를 지우기위해, 이전으로부터 두 줄의 프로시저 LIST-DELETE를 사용한다. 다음 프로시저는 그 list에 한 원소를 삽입한다:
LIST-INSERT'(L,x) 1 x.next = L.nil.next 2 L.nil.next.prev = x 3 L.nil.next = x 4 x.prev = L.nil
그림 10.4는 샘플 list에서 LIST-INSERT'와 LIST-DELETE'의 효과를 보여준다.
Sentinel은 결코 데이터 자료 연산들의 asymptotic time bounds를 줄이지 않는다, 하지만 그것들은 constant factor를 줄일 수 있다. loop 내에서 sentinel을 사용하여 얻는 이익은 보통 속도보다는 오히려 코드의 명확성 문제이다; 예를들어 linked list code는 우리가 sentinel을 사용할 때 더욱 간단해지지만, 우리는 LIST-INSERT'와 LIST-DELETE' 프로시저에서 오직 O(1) 시간을 절약한다. 그러나 다른 상황에서 sentinels의 사용은 루프에서 그 코드를 줄이는데 도움이 된다. 따라서 가령 running time에서 n 또는 n^2의 계수를 줄이다.
우리는 sentinel을 분별력 있게 사용해야만 한다. 많고 작은 리스트들이 있을 때, 센티넬에 의해 사용되는 추가 storage는 큰 낭비되는 메모리를 나타낼 수 있다. 이 책에서, 우리는 그것들이 코드를 진정으로 간결하게 할 때 만 sentinels를 사용한다.
Exercises
10.2-1
너는 singly linked list에서 dynamic-set operation INSERT를 O(1) 시간에만들수 있는가? DELETE는 어떤가?
- INSERT는 앞에 넣어주기만 하면 되서 O(1)이지만, DELETE는 해당 element를 찾아야해서 O(n)이 걸린다.
10.2 -4
쓰여있듯이, LIST-SEARCH' 프로시저 에서 매 loop iteration은 두 가지 테스트를 요구한다: 하나는 x != L.nil이고 하나는 x.key != k이다. 매 반복에서 x != L.nil에대한 테스트가 제거될수있는 보여라.
LIST-SEARCH(L,k)
1 x = L.nil.next
2 L.nil.key = K
3 while x.key != k
4 x = x->next
5 if x = L.nil
6 return NIL
7 else return x
10.2-5
singly linked, circular lists를 사용하여 INSERT, DELETE, 그리고 SEARCH dictionary operations을 구현하라. 너의 프로시저의 런닝 타임은 무엇인가?
* Doubly Linked List
template<class T> class ChanDoublyLinkedList { public: struct Node { Node* prev; T key; Node* next; };
Node* head;
ChanLinkedList() : head(NULL) { }
~ChanLinkedList()
{
Node* cursor = head;
while (cursor != NULL)
{
Node* next = cursor->next;
delete cursor;
cursor = next;
}
}
Node* list_search(const T& key)
{
Node* x = head;
while (x != NULL && x->key != key)
x = x->next;
return x;
}
void list_insert(const T& key)
{
Node* x = new Node;
x->next = head;
if (head != NULL)
head->prev = x;
else
{
tail = x;
}
head = x;
x->prev = NULL;
x->key = key;
}
void list_delete(const T& key)
{
Node* x = list_search(key);
if (x != NULL)
{
if (x->prev != NULL)
x->prev->next = x->next;
else
head = x->next;
if (x->next != NULL)
x->next->prev = x->prev;
delete x;
}
}
};
* Singly Linked List
template<class T> class ChanSinglyLinkedList { public: struct Node { T key; Node* next; }; Node* head; ChanSinglyLinkedList() : head(NULL) { } ~ChanSinglyLinkedList() { Node* cursor = head; while (cursor != NULL) { Node* next = cursor->next; delete cursor; cursor = next; } } Node* list_search(const T& key) { Node* x = head; while (x != NULL && x->key != key) x = x->next; return x; } void list_insert(const T& key) { Node* x = new Node; x->next = head; head = x; x->key = key; } void list_delete(const T& key) { Node* prev = NULL; Node* x = head; while (x != NULL && x->key != key) { prev = x; x = x->next; } if (x != NULL) { if (prev == NULL) head = NULL; else prev->next = x->next; delete x; } } };
* CIrcular Linked List
이것을 구현하기 위해서,
https://www.geeksforgeeks.org/circular-linked-list/
여기 자료도 번역한다.
원형 링크드 리스트는 모든 노드들이 한 원을 형성하기 위해 연결된 링크드 리스트이다. 끝에서 어떠한 NULL이 없다. circular linked list는 singly circulr or doubly circular linked list가 될 수 있다.
원형 연결리스틔 장점:
1) 어떤 노드든지 시작점이 될 수 있다. 우리는 어떤 점에서 든지 시작하여 전체 list를 지나갈수있다. 우리는 그냥 처음 방문된 노드를 다시 방문할 때 멈출 필요가 있다.
2) 큐를 구현하는데 실용적이다. 이 구현과 달리, 만약 우리가 원형 연결리스트를 사용한다면 우리는 front와 rear에 대한 두 포인터를 유지할 필요가 없다. 우리는 마지막에 삽입된 노드에 대한 포인터를 유지할 수 있고, 맨 앞에것은 마지막의 다음것으로 얻어질 수 있다.
3) 원형 리스트는 리스트를 반복적으로 둘러봐야하는 프로그램에서 실용적이다. 예를들어, 많은 프로그램들이 한 PC에서 돌아갈 때, 운영체제가 작동중인 프로그램을 한 list에 넣고 그런다음에 그것들을 통해 cycle하는 것은 흔한 일이다. 이것은 그것들 각각에게 실행한시간의 조각을 주고, 그러고나서 CPU가 다른 프로그램에게 할당되는 동안 기다리게 한다. 운영체제가 그것이 그 list의 끝에 도달했을 때, 그것이 그 리스트의 처음으로 순환하도록 하기 위해 circular list를 사용하는 것은 편리하다.
4) Circular Doubly Linked Lists는 Fibonacci Heap과 같은 고급 자료구조를 구현하기 위해 사용된다.
https://www.geeksforgeeks.org/circular-singly-linked-list-insertion/
Insertion
한 노드는 세 가지 방법으로 더해질 수 있따:
- 비어있는 list에 삽입
- list의 처음에 삽입
- list의 마지막에 삽입
- 노드 사이에 삽입
초기에 그 list가 비어있을 때, last pointer는 NULL일 것이다. node T를 넣은 후에는,
이럴 것이다(그림)
* Singly Circular Linked List
https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/
Circular Doubly Linked List(CDL)은 이중 연결 리스트와 원형 연결리스트 두 개의 특성을 갖는다. 그리고 거기에서 두 개의 연속하는 원소들은 prev과 next 포인터에 의해 연결되어있고 마지막 노드는 next pointer로 첫 번째 노드를 가리키고, 또한 첫 번째 노드는 prev pointer로 마지막 노드를 가리킨다.
* Doubly Circular Linked List
template<class T> class ChanCircularLinkedList {// Singly Circular Linked List public: struct Node { T key; Node* next; }; Node* tail; ChanCircularLinkedList() : tail(NULL) { } ~ChanCircularLinkedList() { if (tail == NULL) return; Node* cursor = tail; do { Node* next = cursor->next; delete cursor; cursor = next; } while (cursor != tail); } Node* list_search(const T& key) { if (tail == NULL) throw runtime_error("There is no element to be searched in the list"); Node* x = tail; do { if (x->key == key) return x; x = x->next; } while (x != tail); return NULL; } void list_insert(const T& key) { Node* x = new Node; x->key = key; if (tail != NULL) { x->next = tail->next; tail->next = x; } else { x->next = x; tail = x; } } void list_delete(const T& key) { if (tail == NULL) throw runtime_error("There is no element to be deleted in the list"); Node* prev = tail; Node* x = tail->next; if (x == tail) { delete x; tail = NULL; return; } do { if (x->key == key) break; prev = x; x = x->next; } while (x != tail->next); if (x->key == key) { prev->next = x->next; if (x == tail) tail = prev; delete x; } } void list_delete(const Node* node) { Node* prev = tail; while (prev->next != node) prev = prev->next; prev->next = node->next; if (node == tail) tail = prev; delete node; if (node == tail) tail = nullptr; node = nullptr; } };
https://www.geeksforgeeks.org/doubly-circular-linked-list-set-1-introduction-and-insertion/
Circular Doubly Linked List(CDL)은 이중 연결 리스트와 원형 연결리스트 두 개의 특성을 갖는다. 그리고 거기에서 두 개의 연속하는 원소들은 prev과 next 포인터에 의해 연결되어있고 마지막 노드는 next pointer로 첫 번째 노드를 가리키고, 또한 첫 번째 노드는 prev pointer로 마지막 노드를 가리킨다.
* Doubly Circular Linked List
template<class T> class ChanCircularLinkedList {// Doubly Circular Linked List public: struct Node { Node* prev; T key; Node* next; }; Node* tail; ChanCircularLinkedList() : tail(NULL) { } ~ChanCircularLinkedList() { if (tail == NULL) return; Node* cursor = tail; do { Node* next = cursor->next; delete cursor; cursor = next; } while (cursor != tail); } Node* list_search(const T& key) { if (tail == NULL) throw runtime_error("There is no element to be searched in the list"); Node* x = tail; do { if (x->key == key) return x; x = x->next; } while (x != tail); return NULL; } void list_insert(const T& key) { Node* x = new Node; x->key = key; if (tail != NULL) { x->prev = tail; x->next = tail->next; tail->next->prev = x; tail->next = x; } else { x->prev = x; x->next = x; tail = x; } } void list_insert_end(const T& key) { if (tail == NULL) list_insert(key); else { Node* x = new Node; x->key = key; x->prev = tail; x->next = tail->next; tail->next->prev = x; tail->next = x; tail = x; } } void list_delete(const T& key) { Node* x = list_search(key); list_delete(x); } void list_delete(Node* node) { if (node != NULL) { node->prev->next = node->next; node->next->prev = node->prev; if (node == tail) tail = node->prev; delete node; if (node == tail) tail = nullptr; node = nullptr; } } };
댓글 없음:
댓글 쓰기