Skip to content

Instantly share code, notes, and snippets.

@zbabtkis
Last active December 31, 2015 02:19
Show Gist options
  • Save zbabtkis/7919690 to your computer and use it in GitHub Desktop.
Save zbabtkis/7919690 to your computer and use it in GitHub Desktop.
Arrayish Linked List in JavaScript
var LinkedList = function () {
"use strict";
var _this = this
, first
, last;
/**
* These hold data and link to the next node.
*
* @param {Object} item Item being added to list.
*/
var Node = function (item) {
return {data: item, next: undefined};
};
/**
* Return node at index.
*
* @param {Integer} ind Requested position in list
* @return {Node} Node at requested position.
*/
var getter = function atIndex (ind) {
var buffer;
for(var i = 0; i <= ind; i++) {
buffer = buffer ? buffer.next : first;
}
return buffer;
}
// Holds the count of all currently linked nodes.
getter.count = 0;
/**
* Add a node to the linked list
*
* @param {Object} item Data to add to linked list as node.
*/
getter.add = function (item) {
var node = new Node(item);
if(!first) first = node;
// The last node should link to this node.
if(last) last.next = node;
// The final node in the list should link back to the first.
node.next = first;
last = node;
this.count++;
};
/**
* Remove last item from linked list
*
* return {Object} last item that no longer exists in list.
*/
getter.pop = function () {
var previous
, popped;
if(this.count > 1) {
previous = getter(this.count - 2);
popped = previous.next;
// Remove pointer to last item so it can be garbage collected.
previous.next = first;
last = previous;
this.count--;
} else {
first = undefined;
last = undefined;
this.count = 0;
}
return popped;
};
/**
* Remove all items from list (good for destroying data)
*/
getter.empty = function () {
for(var i = 0; i < this.count; i++) {
this.pop();
}
};
return getter;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment