Data Structures: Doubly Linked Lists

What is a doubly linked list?

A doubly linked list is a sequential data structure where every value is encapsulated into a structure that links to next and previous structure. Taken this linking chain together, these structures allocated at random RAM positions form the appearance of a sequence whose SIZE is known. For everything to work properly, doubly linked list must keep track of HEAD and TAIL entry, each able to function as linking chain's start point for forward/backward traversal.

How does it work?

As a sequential data structure, doubly linked list can be used to implement many abstract data types. Let us take its List implementation as an example to understand how it works:

Operation Description
addToHead Encapsulates VALUE, links itself to old HEAD (if exists), makes itself HEAD, then increments SIZE.
addToTail Encapsulates VALUE, links old TAIL to itself, makes itself TAIL, then increments SIZE.
clear Loops through the linking chain, dealocates every structure found, resets SIZE to zero.
containsIndex Checks if position is smaller than SIZE.
containsValue Loops through the linking chain and checks if any value of entry equals VALUE by COMPARATOR.
emplace Encapsulates VALUE, loops through the linking chain until POSITION is reached, links entry at POSITION-1 to itself, links itself to entry at POSITION, then increments SIZE.
get Loops through the linking chain and returns value of entry found at POSITION.
set Loops through the linking chain and modifies value of entry found at POSITION with VALUE.
removeIndex Loops through the linking chain until POSITION is reached, links entry found at POSITION-1 to that at POSITION+1, deallocates entry found at POSITION then decrements SIZE.
removeValue Loops through the linking chain keeping track of position. If entry value matches VALUE by COMPARATOR makes previous entry link to next entry, deallocates matching entry then decrements SIZE.
isEmpty Checks if SIZE equals zero
size Gets SIZE value

Compared to Dynamic Array as List implementation, doubly linked list thus fits a very different profile:


Share