하나의 노드에 자신의 앞에 있는 포인트와 그 자신의 뒤에 있는 노드의 포인트를 연결시킨 구조로 여러 노드들이 포인터로 연결된 연결 리스트구조로 단일연결리스트와는 다르게 리드를 전방 혹은 후방의 양방향으로 탐색이 가능하고 노드의 삽입이나 삭제가 쉽다는 장점을 갖습니다.
아래와 같은 구조를 갖고 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13 |
var firstNode = {
data: 12,
next: null,
prev: null
};
var secondNode = {
data: 99,
prev: firstNode, //set pointer #1
next: null
};
firstNode.next = secondNode; //set pointer #2 |
이러한 단일 연결구조를 나타내는 프로토타입을 만들어 보겠습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87 |
function DoublyLinkedList(){
this._length = 0;
this._head = null;
this._tail = null;
}
DoublyLinkedList.prototype = {
add: function(data){
var node = {
data: data,
next: null,
prev: null,
};
if(this._length == 0){
this._head = node;
this._tail = node;
}
else{
this._tail.next = node;
node.prev = this._tail;
this._tail = node;
}
this._length++;
},
item: function(index){
if (index > -1 && index < this._length){
var current = this._head,
i = 0;
while(i++ < index){
current = current.next;
}
return current.data;
}
else {
return null;
}
},
remove: function(index){
if(index > -1 && index < this._length){
var current = this._head,
i = 0;
if(index === 0){
this._head = current.next;
if(!this._head){
this._tail = null;
}
else{
this._head.prev = null;
}
}
else if(index === this._length-1){
current = this._tail;
this._tail = current.prev;
this._tail.next = null;
}
else{
while(i++ < index){
current = current.next;
}
current.prev.next = current.next;
}
this._length--;
return current.data;
}
else{
return null;
}
}
};
var list = new DoublyLinkedList();
list.add("red");
list.add("orange");
list.add("yellow");
console.log(list); |
콘솔창에 결과를 확인해 보면 다음과 같습니다.
출처 : http://www.nczonline.net/blog/2009/04/21/computer-science-in-javascript-doubly-linked-lists/
'IT > 기타' 카테고리의 다른 글
| MSSQL MDB변환 (0) | 2015.06.08 |
|---|---|
| 반응형 웹 (0) | 2014.12.01 |
| 환형 연결 리스트 [circular linked list] (0) | 2014.11.25 |
| mysql group_concat함수의 길이 제한 (0) | 2014.11.25 |
| split join을 이용한 메뉴 만들기 (0) | 2014.04.14 |
