연결리스트에 대한 설명은 위키디피아에 되어 있습니다.
연결리스트 중에 단일 연결 리스트는 리스트의 각 노드에 다른 노드를 가리키는 포인터가 하나씩만 있는 연결 리스트입니다.
포인터는 특정 자료구조의 주소를 저장해놓고 기억하고 있는 역할을 합니다.
우선 단일 연결리스트는 다음과 구조를 같게 됩니다.
첫번째 자료의 포인터가 두번째 자료를 가리키고 두번째 자료의 포인터가 세번째 자료를 가리키는 이러한 형태가 반복됩니다.
위 그림을 자바스크립트로 간단하게 표현해 보면 아래와 같습니다.
|
1
2
3
4
5
6
7
8
9 |
var firstNode = {
data:12,
next:null
};
firstNode.next = {
data:99,
next:null
}; |
이러한 단일 연결구조를 나타내는 프로토타입을 만들어 보겠습니다.
|
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 LinkedList(){
this._length = 0;
this._head = null;
}
LinkedList.prototype = {
add: function(data){
var node = {
data:data,
next:null
},
current;
if(this._head === null){
this._head = node;
}
else{
current = this._head;
while(current.next){
current = current.next;
}
current.next = 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,
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 LinkedList();
list.add("red");
list.add("orange");
list.add("yellow");
console.log(list); |
결과값을 콘솔에서 확인해보면
각 자료구조가 포인터를 통해 연결되 있는 것을 확인 할 수 있습니다.
참조 : http://www.nczonline.net/blog/2009/04/13/computer-science-in-javascript-linked-list/
'IT > 개발' 카테고리의 다른 글
| iframe 부모 자식 접근 (0) | 2014.11.28 |
|---|---|
| php 일단위로 for문 돌리기 (0) | 2014.11.26 |
| 자바스크립트 패턴 (0) | 2014.05.18 |
| php 배열 관련 함수 (0) | 2014.04.16 |
| php call by reference & php call by value (0) | 2014.04.15 |
