forked from behappyyoung/javascriptsamplecodes
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDouble_linked_list.js
More file actions
120 lines (90 loc) · 3.3 KB
/
Copy pathDouble_linked_list.js
File metadata and controls
120 lines (90 loc) · 3.3 KB
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/**
* Created by young on 5/27/14.
* * double linked list implementation
*/
function DoublyLinkedList() {
this._length = 0;
this._head = null;
this._tail = null;
this.add= function (data){
//create a new item object, place data in
var node = {
data: data,
next: null,
prev: null
};
//special case: no items in the list yet
if (this._length === 0) {
this._head = node;
this._tail = node;
} else {
//attach to the tail node
this._tail.next = node;
node.prev = this._tail;
this._tail = node;
}
//don't forget to update the count
this._length++;
};
this.remove= function(index){
//check for out-of-bounds values
if (index > -1 && index < this._length){
var current = this._head,
i = 0;
//special case: removing first item
if (index === 0){
this._head = current.next;
/* */
if (!this._head){
this._tail = null;
} else {
this._head.prev = null;
}
//special case: removing last item
} else if (index === this._length -1){
current = this._tail;
this._tail = current.prev;
this._tail.next = null;
} else {
//find the right location
while(i++ < index){
current = current.next;
}
//skip over the item to remove
current.prev.next = current.next;
}
//decrement the length
this._length--;
//return the value
return current.data;
} else {
return null;
}
};
this.showList =function(){
var showText = ' => ';
var current = this._head;
while(current!=null){
showText += ' <- ' + current.data + ' -> ' ;
current = current.next;
}
return showText+ "<== ";
}
}
var mydlink = new DoublyLinkedList();
var div = document.getElementById('display');
div.innerHTML += 'start length : ' + mydlink._length + ' ---' + mydlink.showList() + '<br />';
mydlink.add('first');
div.innerHTML += 'add first [mydlink.add("first") ]- length: ' + mydlink._length + ' ---' + mydlink.showList() + '<br />';
mydlink.add('second');
div.innerHTML += 'add second [mydlink.add("second") ]- length: ' + mydlink._length + ' ---' + mydlink.showList() + '<br />';
mydlink.add('third');
div.innerHTML += 'add third [mydlink.add("third") ]- length: ' + mydlink._length + ' ---' + mydlink.showList() + '<br />';
div.innerHTML += 'head => : ' + mydlink._head.data + '<br />';
div.innerHTML += 'tail => : ' + mydlink._tail.data + '<br />';
div.innerHTML += 'head . next => : ' + mydlink._head.next.data + '<br />';
mydlink.remove(1);
div.innerHTML += 'remove(index) [mydlink.remove(1)] : ---' + mydlink.showList() + '<br />';
div.innerHTML += 'head => : ' + mydlink._head.data + '<br />';
div.innerHTML += 'head . next => : ' + mydlink._head.next.data + '<br />';
div.innerHTML += 'tail => : ' + mydlink._tail.data + '<br />';