Last active
October 4, 2016 13:45
-
-
Save tk120404/9091392 to your computer and use it in GitHub Desktop.
LinkedList implemenation in Javascript
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var LinkedList = function() | |
{ | |
this._head = this._tail = null; | |
this._transverse = null; | |
this._size = 0; | |
} | |
function QEntry(prev, obj, next) | |
{ | |
if (typeof obj === 'undefined' || obj === null) { | |
throw new Error('Null or Undefined values are not supported'); | |
} | |
this.item = obj; | |
this.prev = prev; | |
this.next = next; | |
} | |
LinkedList.prototype.push = function(item) | |
{ | |
var tail = this._tail, | |
entry = new QEntry(tail, item, null); | |
if (!this._head) { | |
this._head = entry; | |
} else { | |
tail.next = entry; | |
} | |
this._tail = entry; | |
this._size++; | |
return true; | |
} | |
LinkedList.prototype.offerLast = LinkedList.prototype.push; | |
LinkedList.prototype.insertAfter = function(entry, item) | |
{ | |
if(!entry.next) | |
{ | |
this.push(item) | |
} | |
else | |
{ | |
var newEntry = new QEntry(entry,item,entry.next); | |
this._size++; | |
(entry.next).prev = newEntry; | |
entry.next = newEntry; | |
} | |
} | |
LinkedList.prototype.insertBefore = function(entry, item) | |
{ | |
if(!entry.prev) | |
{ | |
this.offerFirst(item); | |
} | |
else | |
{ | |
var newEntry = new QEntry(entry.prev,item,entry); | |
this._size++; | |
(entry.prev).next = newEntry; | |
entry.prev = newEntry; | |
} | |
} | |
LinkedList.prototype.deleteAt = function(list,entry) | |
{ | |
var next = entry.next, | |
prev = entry.prev; | |
if(!prev) | |
list._head = next; | |
else | |
prev.next = next; | |
if(!next) | |
list._tail = prev; | |
else | |
next.prev = prev; | |
list._transverse = prev; | |
this._size--; | |
delete entry; | |
} | |
LinkedList.prototype.pop = function() | |
{ | |
var ret = this._tail, | |
prev = ret.prev; | |
if (!prev) { | |
this._head = this._tail = null; | |
} else { | |
prev.next = null; | |
ret.prev = null; | |
} | |
this._tail = prev; | |
this._size--; | |
return ret.item; | |
} | |
LinkedList.prototype.popLast = LinkedList.prototype.pop; | |
LinkedList.prototype.unshift = function(item) | |
{ | |
var head = this._head, | |
entry = new QEntry(null, item, head); | |
if (!this._tail) { | |
this._tail = entry; | |
} else { | |
head.prev = entry; | |
} | |
this._head = entry; | |
this._size++; | |
return true; | |
} | |
LinkedList.prototype.offerFirst = LinkedList.prototype.unshift; | |
LinkedList.prototype.shift = function() | |
{ | |
if (this._size <= 0) return null; | |
var ret = this._head, | |
next = ret.next; | |
if (!next) { | |
this._head = this._tail = null; | |
} else { | |
next.prev = null; | |
ret.next = null; | |
} | |
this._head = next; | |
this._size--; | |
return ret.item; | |
} | |
LinkedList.prototype.popFirst = LinkedList.prototype.shift; | |
LinkedList.prototype.toArray = function() | |
{ | |
var head = this._head, | |
arr = []; | |
while (head) { | |
arr.push(head.item); | |
head = head.next; | |
} | |
return arr; | |
}; | |
LinkedList.prototype.next = function() | |
{ | |
if (this._size <= 0) return null; | |
if (!this._transverse) { | |
this._transverse = this._head; | |
} else if (this._transverse.next) { | |
this._transverse = this._transverse.next; | |
} else { | |
return null; | |
} | |
return this._transverse; | |
} | |
LinkedList.prototype.prev = function() | |
{ | |
var transverse = this._transverse; | |
if (!transverse) { | |
return null | |
} else if (transverse.prev) { | |
this._transverse = transverse.prev; | |
transverse = this._transverse; | |
} | |
else | |
{ | |
this._transverse = null; | |
return null; | |
} | |
return transverse; | |
} | |
LinkedList.prototype.item = function() | |
{ | |
if (!this._transverse) { | |
this._transverse = this._head; | |
} | |
return this._transverse.item; | |
} | |
LinkedList.prototype.current = function() | |
{ | |
if (!this._transverse) { | |
this._transverse = this._head; | |
} | |
return this._transverse; | |
} | |
LinkedList.prototype.first = function() | |
{ | |
return this._head; | |
} | |
LinkedList.prototype.last = function() | |
{ | |
return this._tail; | |
} | |
LinkedList.prototype.length = function() | |
{ | |
return this._size; | |
} | |
var ll = new LinkedList(); | |
var temp = { | |
'val':'Ram', | |
'type':'String' | |
}; | |
ll.push('1'); | |
ll.push('2'); | |
ll.push('3'); | |
ll.push(temp); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment