Skip to content

Instantly share code, notes, and snippets.

@tk120404
Last active October 4, 2016 13:45
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tk120404/9091392 to your computer and use it in GitHub Desktop.
Save tk120404/9091392 to your computer and use it in GitHub Desktop.
LinkedList implemenation in Javascript
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