일반적인 연결 리스트 구조는 처음 노드와 마지막 노드가 분명하게 구분되는선형 리스트인데 마지막 노드의 LINK 필드값은 항상 「(null)」이었다. 이와 같은 선형 리스트를 좀 더 융통성있게 처리하고 마지막 노드의 LINK 필드를 활용하기 위해서 마지막 노드의 LINK 필드가 null이 아닌 첫 번째 노드의 주소를 지적하도록 리스트를 구성할 수 있는데, 이렇게 구성된 리스트를 환형 연결 리스트라 합니다
단일 환형 연결 리스트
위 그림을 간략하게 자바스크립트로 표현 하면 다음과 같습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12 |
var firstNode = {
data: 12,
next: null,
};
firstNode.next = firstNode;
var secondNode = {
data: 99,
next: null
};
firstNode.next = secondNode;
secondNode.next = firstNode; |
프로토타입을 만들어 보겠습니다.
|
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 |
function CircularLinkedList(){
this._length = 0;
this._head = null;
}
CircularLinkedList.prototype = {
add: function(data){
var node = {
data:data,
next:null
},
current;
if(this._head === null){
node.next = node;
this._head = node;
}
else{
current = this._head;
while(!(current.next==this._head)){
current = current.next;
}
current.next = node;
node.next = this._head;
}
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,
previous,
i=0;
if(index === 0){
this._head = current.next;
}
else{
while(i++ < index){
previous = current;
current = current.next;
}
previous.next = current.next;
}
this._length--;
return current.data;
}
else{
return null;
}
}
};
var list = new CircularLinkedList();
list.add("red");
list.add("orange");
list.add("yellow");
console.log(list); |
이중 환형 연결 리스트
위 그림을 간략하게 자바스크립트로 표현 하면 다음과 같습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 |
var firstNode = {
data: 12,
next: null,
prev: null
};
firstNode.next = firstNode;
firstNode.prev = firstNode;
var secondNode = {
data: 99,
prev: firstNode,
next: null
};
firstNode.prev = secondNode;
firstNode.next = secondNode;
secondNode.prev = firstNode;
secondNode.next = firstNode; |
프로토타입을 만들어 보겠습니다.
|
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
88
89
90
91
92
93
94 |
function CircularDoublyLinkedList(){
this._length = 0;
this._head = null;
this._tail = null;
}
CircularDoublyLinkedList.prototype = {
add: function(data){
var node = {
data: data,
next: null,
prev: null,
};
if(this._length == 0){
node.prev = node;
node.next = node;
this._head = node;
this._tail = node;
}
else{
node.next = this._tail.next;
node.prev = this._tail;
this._tail.next.prev = node;
this._tail.next = node;
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 = this._tail;
this._tail.next = this._head;
}
}
else if(index === this._length-1){
current = this._tail;
this._tail = current.prev;
this._tail.next = current.next;
this._head.prev = this._tail;
}
else{
while(i++ < index){
current = current.next;
}
current.next.prev = current.prev;
current.prev.next = current.next;
}
this._length--;
return current.data;
}
else{
return null;
}
}
};
var list = new CircularDoublyLinkedList();
list.add("red");
list.add("orange");
list.add("yellow");
console.log(list); |
'IT > 기타' 카테고리의 다른 글
| MSSQL MDB변환 (0) | 2015.06.08 |
|---|---|
| 반응형 웹 (0) | 2014.12.01 |
| 이중 연결 리스트 [doubly linked list] (0) | 2014.11.25 |
| mysql group_concat함수의 길이 제한 (0) | 2014.11.25 |
| split join을 이용한 메뉴 만들기 (0) | 2014.04.14 |
