Double Linked List

Now one issue that linked lists have is that while it’s really easy to move to the next element in your list, moving backwards to find the previous item is really challenging. You literally have to start back at the beginning and move through every element, until you reach the one before where you just were.

While this isn’t an issue if you only have a dozen elements in your list, when you get a thousand, or more, it can be quite a resource hog, especially if you have to constantly do this.

An easy fix for this, is the double linked list. It is very similar to the linked list, except instead of one pointer, pointing to the next item, each element has two pointers. One points to the next item in the list like before, and the second pointer points to the previous item in the list.

Inserting an item in the list is generally not much more difficult. You just need to update two pointers instead of one.

However, you don’t have to start at the beginning of the list. You can move forward and backward with just a little bit of extra code to determine where you should move to next.

Class DoubleLinkedListItem {
  DoubleLinkedListItem nextObject;
  DoubleLinkedListItem previousObject;
  Object data;

  Object getNextObject() {
    return this.nextObject;
  }
  Object getPreviousObject() {
    return this.previousObject;
  }
  void setNextObject(Object newObject) {
    this.nextObject = newObject;
  }
  void setPreviousObject(Object newObject) {
    this.previousObject = newObject;
  }
  void insertNewObject(Object newObject) {
    newObject.setPreviousObject(this.getPreviousObject());
    newObject.setNextObject(this);
    this.setPreviousObject(newObject);
    this.getPreviousObject().setNextObject(newObject);
  }
}

Class DoubleLinkedListItem {
DoubleLinkedListItem nextObject;
DoubleLinkedListItem previousObject;
Object data;

Object getNextObject() {
return this.nextObject;
}
Object getPreviousObject() {
return this.previousObject;
}
void setNextObject(Object newObject) {
this.nextObject = newObject;
}
void setPreviousObject(Object newObject) {
this.previousObject = newObject;
}
void insertNewObject(Object newObject) {
newObject.setPreviousObject(this.getPreviousObject());
newObject.setNextObject(this);
this.setPreviousObject(newObject);
this.getPreviousObject().setNextObject(newObject);
}
}

You will still need to use the current object pointer, just like you did with your linked list, and depending upon its use, you may want to have a start, or top pointer. Of course, you can get rid of that, if you assume that the list is circular, and your last element points to your first as the next, and first points to the last element. This is sometimes referred to as a circular list, but is rarely seen in production.

Because it is a fairly simple upgrade in logic, and only costs a little more in memory usage, a lot of developers will opt for the double linked list as it can make working with your data types much faster, especially given the minimal “cost” of memory.

Double Linked List was originally found on Access 2 Learn