Data Structures: Linked Lists

What is a linked list?

A linked list is a sequential data structure where every value is encapsulated into a structure that links to a next 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, linked list must keep track of HEAD entry, which will always be linking chain's start point.

How does it work?

As a sequential data structure, 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, loops through the linking chain until it finds an entry that links nowhere, links that entry to itself 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-1 is reached, links entry found there to itself, links itself to entry found 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-1 is reached, links entry found to that at POSITION+1, deallocates entry found at POSITION then decrements SIZE.
removeValue Loops through the linking chain keeping track of position. If next entry value matches VALUE by COMPARATOR, deallocates matching entry, links entry at POSITION-1 to that at POSITION+1 then decrements SIZE.
isEmpty Checks if SIZE equals zero
size Gets SIZE value

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


Share