Circular Doubly Linked List object

10th January 2014

There are some data types that are available in languages like C# or Java that you expect from high level languages. Data types are very important when it comes to intensive tasks, like computer graphics for example. The differences in the implementations can have huge impact on the performance of the underlying code. The Javascript object below can be used to implement a circular doubly linked list.

What is it?

A circular structure is one that loops back on itself. So a circular array would consist of the last item pointing back to the first as the next item in the array. A linked list refers to a pointer being used in each item that points to the next item, so that if you have one item, you can get to the next by simply looking up the value from memory using a reference. A doubly linked list refers to a list where each item has a reference to its next and previous items so you can traverse through the list from any point quickly.

Javascript

You can find the whole code below. Two new classes are introduced: a 'CircularDoublyLinkedList' and 'CircularDoublyLinkedListItem':

//fast indexing and creation for a double-sided linked list
//fast insertion for push/pop/shift/unshift, fast traveral via .next/.prev and fast size calculation using '.length'
//first and last elements have cyclic links back the last and first elements
function CircularDoublyLinkedList() {
this.length = 0;
this.first = null;
this.last = null;
}

CircularDoublyLinkedList.fromArray = function(arr) {
//make a double-linked list quickly from the elements
var newlist = new CircularDoublyLinkedList();

if (arr.length>1) {
var items = [];

//create the item wraps
arr.forEach(function(val) {
items.push(new CircularDoublyLinkedListItem(newlist, val));
});

//create the links between items
var numItems = items.length;
var firstItem = items[0];
var lastItem = items[numItems-1];

firstItem.prev = lastItem;
lastItem.next = firstItem;

for (var i=0, j=1; j<numItems; i++, j++) {
items[i].next = items[j];
items[j].prev = items[i];
}

newlist.first = firstItem;
newlist.last = lastItem;
newlist.length = numItems;
} else if (arr.length) {
newlist.push(arr[0]);
}

return newlist;
};

CircularDoublyLinkedList.prototype = {
forEach: function(func) {
var currItem = this.first;

while (currItem) {
func(currItem, this);

if (currItem.isLast()) {
break;
}

currItem = currItem.next;
}
},
toArray: function() {
var arr = [];

this.forEach(function(val) {
arr.push(val.item);
});

return arr;
},
clear: function() {
this.first = null;
this.last = null;
this.length = 0;
},
//attach one double linked list to the end of this one
//note: changes the given second linked list
//note: rather than change all references to the items to this list, we make the two arrays the same
prepend: function(arr2) {
//note: changes the given second linked list
arr2.last.next = this.first;
this.first.prev = arr2.last;
arr2.first.prev = this.last;
this.last.next = arr2.first;

this.first = arr2.first;
arr2.last = this.last;
this.length += arr2.length;
},
append: function(arr2) {
arr2.last.next = this.first;
this.first.prev = arr2.last;
arr2.first.prev = this.last;
this.last.next = arr2.first;

this.last = arr2.last;
arr2.first = this.first;
this.length += arr2.length;
},
unshift: function(item) {
if (this.first) {
this.first.insertBefore(item);
} else {
var newItem = new CircularDoublyLinkedListItem(this, item);
newItem.prev = newItem.next = newItem;
this.first = this.last = newItem;
this.length = 1;
}
},
shift: function() {
if (this.first) {
this.first.remove();
}
},
push: function(item) {
if (this.last) {
this.last.insertAfter(item);
} else {
var newItem = new CircularDoublyLinkedListItem(this, item);
newItem.prev = newItem.next = newItem;
this.first = this.last = newItem;
this.length = 1;
}
},
pop: function() {
if (this.last) {
this.last.remove();
}
}
};

function CircularDoublyLinkedListItem(list, item, next, prev) {
this.list = list;
this.item = item;

this.next = next;
this.prev = prev;
}

CircularDoublyLinkedListItem.prototype = {
isFirst: function() {
return this.list.first===this;
},
isLast: function() {
return this.list.last===this;
},
insertAfter: function(item) {
var newItem = new CircularDoublyLinkedListItem(this.list, item, this.next, this);
this.list.length++;

this.next.prev = newItem;

if (this.isLast()) {
this.list.last = newItem;
}

this.next = newItem;
},
insertBefore: function(item) {
var newItem = new CircularDoublyLinkedListItem(this.list, item, this, this.prev);
this.list.length++;

this.prev.next = newItem;

if (this.isFirst()) {
this.list.first = newItem;
}

this.prev = newItem;
},
remove: function() {
this.prev.next = this.next;
this.next.prev = this.prev;

if (this.isFirst()) {
if (this.next && this.next!==this) {
this.list.first = this.next;
} else {
this.list.first = null;
}
}

if (this.isLast()) {
if (this.prev && this.prev!==this) {
this.list.last = this.prev;
} else {
this.list.last = null;
}
}

this.list.length--;

//remove all of the references in this object that we are trying to remove (which may contain self references)
this.list = null;
this.next = null;
this.prev = null;
this.item = null;

delete this.list;
delete this.next;
delete this.prev;
delete this.item;
}
};

Usage

Typical usage of the class above is defined below:

var list = CircularDoublyLinkedList.fromArray([1,2,3,4,5,6]);
console.log(list.last.prev.prev.prev.next.prev.item);
console.log(list.toArray());

Comments

I wish this website had reviews :(
luiz - 20th May 2014 16:07
@luiz What sort of reviews would you like to see?
Andrew Lowndes - 23rd May 2014 18:05

Make a comment

Contribute to this article and have your say.