So I was playing around with the linked list in JS and came up with the following question:
Lets say, that we have an array and a linked list both with 5000 elements. We want to insert new element at index 10. The array way is pretty simple. We insert the new element at the given index and move the rest of the elements one index forward. So I tried doing this with linked list and end it up with the following:
Getting the implementation of linked list from Nicholas Zakas and adding additional method addOnPosition(data,index). At the end here is the code:
function LinkedList() {
this._head = null;
this._length = 0;
}
LinkedList.prototype = {
constructor: LinkedList,
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++;
},
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;
}
},
item: function(index) {
var current = this._head,
i = 0;
if (index > - 1 && index < this._length) {
while (i++ < index) {
current = current.next;
}
return current.data;
}
else {
return null;
}
},
addOnPosition: function(data,index) {
if (index > -1 && index <= this._length) {
var node = {
data: data,
next: null
},
current = this._head,
i = 0,
temp,
previous;
if (this._head === null) {
this._head = node;
}
else {
if (index === 0) {
this._head = node;
node.next = current;
}
else {
while (i++ < index) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
}
}
this._length++;
}
else {
return null;
}
},
toArray: function() {
var result = [],
current = this._head;
while (current) {
result.push(current.data);
current = current.next;
}
return result;
},
toString: function() {
return this.toArray().toString();
}
}
At the end, my question is: Is this method faster than doing all this with array and if it is, what is the plexity for both? And probably the more important, did I missed something with the adOnPosition method implementation?
So I was playing around with the linked list in JS and came up with the following question:
Lets say, that we have an array and a linked list both with 5000 elements. We want to insert new element at index 10. The array way is pretty simple. We insert the new element at the given index and move the rest of the elements one index forward. So I tried doing this with linked list and end it up with the following:
Getting the implementation of linked list from Nicholas Zakas and adding additional method addOnPosition(data,index). At the end here is the code:
function LinkedList() {
this._head = null;
this._length = 0;
}
LinkedList.prototype = {
constructor: LinkedList,
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++;
},
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;
}
},
item: function(index) {
var current = this._head,
i = 0;
if (index > - 1 && index < this._length) {
while (i++ < index) {
current = current.next;
}
return current.data;
}
else {
return null;
}
},
addOnPosition: function(data,index) {
if (index > -1 && index <= this._length) {
var node = {
data: data,
next: null
},
current = this._head,
i = 0,
temp,
previous;
if (this._head === null) {
this._head = node;
}
else {
if (index === 0) {
this._head = node;
node.next = current;
}
else {
while (i++ < index) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
}
}
this._length++;
}
else {
return null;
}
},
toArray: function() {
var result = [],
current = this._head;
while (current) {
result.push(current.data);
current = current.next;
}
return result;
},
toString: function() {
return this.toArray().toString();
}
}
At the end, my question is: Is this method faster than doing all this with array and if it is, what is the plexity for both? And probably the more important, did I missed something with the adOnPosition method implementation?
Share Improve this question asked Aug 26, 2013 at 10:11 sla55ersla55er 8111 gold badge10 silver badges17 bronze badges 1-
1
Why didn't you use the
itemmethod to select the index in addOnPosition (seems like you're repeating yourself)? This could be faster for large lists, why don't you write a test on jsperf.? – RoryKoehein Commented Aug 26, 2013 at 10:25
2 Answers
Reset to default 10See http://en.wikipedia/wiki/Dynamic_array#Performance for plexity of LinkedList and ArrayList data structures. For funzies, also check out When to use LinkedList over ArrayList?
Inserting after a node in a singly-linked list is a constant-time operation. If you have a node in a doubly-linked list, inserting before it is also a constant-time operation.
However, your addOnPosition function runs down the linked list 'index' times; that is, you jump from one node to the next that many times. As such, your algorithm's plexity is basically O(index) - we'd write that as O(n).
To explain my point: If you wish to insert a node at the 0th element, your operation basically runs at constant time; you get the this._front node and you're done. To insert to the end of your linear, singly-linked list, you must iterate down to the end of the list, performing more "jumps" from one node to the next. You can use circular linked lists to optimize this case.
As for performing a similar insertion with an arraylist, insertion plexity is basically O(length - index) as length-index elements must be shifted down the array, we write this as O(n).
Actually insertion into the middle of a linked list is O(n) time plexity, meaning the time it will take on average or in the worst case is proportional to the number of elements already in the list (i.e. n). "O(index)" is not even a real time plexity.
The time plexity for inserting into the middle of an array is also O(n). "O(length - index)" is also not a real time plexity. The number of operations involved in shifting elements in the list in the average or worst case is going to be proportional to the number of items in the list (i.e. n).
The advantage to a linked list over an array is that prepending/appending elements to the front/back of the list is O(1) time plexity, but O(n) for an array.
The advantage of an array over a linked list is that retrieving an element from an array by it's index is O(1), but O(n) for a linked list.
The simplest way to decide between a linked list and an array, is to determine if you need fast appending/prepending or fast index based retrieval of data. If you need both, then there are some variations on these data structures that provide good performance/promises in both areas.