Moshe's Blog

Tips and tricks learnt along the way.

Circular Doubly Linked List

| Comments

I was working on a cycling plugin for javascript and kept getting bogged down by accessing the prev and next elements in the array. I kept having to do things like:

function step() {
    var currentItem = items[currentIndex];
    var nextItem = items[(currentIndex + 1) % items.length];
    var prevItem = items[(items.length + currentIndex - 1) % items.length];
    // more code
    index = (index + 1) % items.length
}

While this is doable it just seems like a pain.
Giving it more thought I realized that a circular doubly linked list would be a great solution to this:



var list = [{label: 'first'}, {label: 'second'}, {label: 'third'}];
var circled = circleLink(list);

assert(circled[0].next === circled[1]);
assert(circled[1].next === circled[2]);
assert(circled[2].next === circled[0]);

assert(circled[0].prev === circled[2]);
assert(circled[1].prev === circled[0]);
assert(circled[2].prev === circled[1]);

document.write(circled[0].index + '<br>');
document.write(circled[1].index + '<br>');
document.write(circled[2].index + '<br>');
document.write(circled[0].next.next.next.prev.prev.index + '<br>');

function circleLink(array) {
  var linkedListCircle = []
  for (var i = 0; i < array.length; i++) {
    linkedListCircle[i] = array[i];
    linkedListCircle[i].index = i;
    if (i > 0) {
      linkedListCircle[i].prev = linkedListCircle[i - 1];
    }
  }
  linkedListCircle[0].prev = linkedListCircle[i - 1]
  for (var i = 0; i < array.length - 1; i++) {
    linkedListCircle[i].next = linkedListCircle[i + 1];
  }
  linkedListCircle[i].next = linkedListCircle[0];
  return linkedListCircle;
}
function assert(assertion) { document.write((assertion ? true : false) + '<br>') }

See the Pen %= penName %> by Moshe Kolodny (@kolodny) on CodePen

Comments