Data Structures: Linked List

a guide into data structures and the most known related algorithms

In this article, I am explaining my second data structure, and I will be writing about more popular data structures in upcoming articles.
These articles assume our readers are familiar with the concept of data structures and why they are used in software development, and it will dive into the definition, the different types, implementations, and complexity of each data structure we are studying.

Definition

A Linked List is a sequential list of nodes (Objects) containing data and pointing to another (usually the next) node that also contains data.
Below is a list of terms we use when talking about linked lists and their corresponding definitions.

Head: is the first node in a linked list, it points to the first next node in the list.

Tail: is the last node in a linked list, it points to null.

Pointer: is the reference of the next node.

Node: is an object containing data and a pointer to another node.

Linked lists keep a reference of their Head and Tail nodes to make it easier to add and remove nodes.

Usage

1- Used in Lists, Queue, and Stack implementations.

2- For creating circular lists, modeling repeating event cycles.

3- For modeling real-world objects.

4- For hashtable separate chaining.

5- For implementing adjacency lists for graphs.

Types

There are two main types of linked lists, singly and doubly.

Singly linked-lists hold a reference to the next node only, whether the doubly linked-lists hold two references one for the next node and another for the previous node.

Pros and Cons

While Singly linked-lists are easier to implement and use less memory, they don’t offer easy access to previous nodes.

On the other hand, doubly linked-lists can be traversed backward, yet they occupy 2 times space in memory.

Time Complexity

Different operations in a Liked List have different time complexities. the table below shows the big O notation for the different possible operations in both singly and doubly linked-lists.

Linked Lists in different programming languages

Unlike Arrays, not many languages offer Linked List as a data structure, so you might find yourself in need to implement it yourself.

JAVA

JAVA offers a linked list type to be used along with some helper methods:

LinkedList<String> cars = new LinkedList<String>();
    cars.add("Volvo");
    cars.add("BMW");
    cars.add("Ford");

addFirst(): Adds an item to the beginning of the list.
addLast(): Adds an item to the end of the list.
removeFirst(): Removes an item from the beginning of the list.
removeLast(): Removes an item from the end of the list.
getFirst(): Gets the item at the beginning of the list.
getLast(): Gets the item at the end of the list.

C#

Similarily to JAVA, C# offers an implementation of LinkedList with properties and methods:

// Create the link list. 
string[] words = { “the”, “fox”, “jumps”, “over”, “the”, “dog” }; LinkedList<string> sentence = new LinkedList<string>(words);

The methods offered by C# are more expansive but I will just show some for now.

AddAfter(node1, node2): Adds the specified new node after the specified existing node in the LinkedList<T>.

AddBefore(node1, node2): Adds the specified new node before the specified existing node in the LinkedList<T>.

AddFirst(node): Adds the specified new node at the start of the LinkedList<T>.

AddFirst(T): Adds a new node containing the specified value at the start of the LinkedList<T>.

AddLast(node): Adds the specified new node at the end of the LinkedList<T>.

AddLast(T): Adds a new node containing the specified value at the end of the LinkedList<T>.

Clear(): Removes all nodes from the LinkedList<T>.

Contains(T): Determines whether a value is in the LinkedList<T>.

FindLast(T): Finds the last node that contains the specified value.

Remove(node): Removes the specified node from the LinkedList<T>.

Remove(value): Removes the first occurrence of the specified value from the LinkedList<T>.

RemoveFirst(): Removes the node at the start of the LinkedList<T>.

RemoveLast(): Removes the node at the end of the LinkedList<T>.

Ruby/Python/JavaScript

Languages like Ruby, Python, and JavaScript don’t offer a packaged implementation, but it is always easy to write our own.

I will use Python for my example below:

# A simple Python program to introduce a linked list
# Node class
class Node:
   # Function to initialise the node object
   def __init__(self, data):
      self.data = data  # Assign data
      self.next = None  # Initialize next as null
# Linked List class contains a Node object
class LinkedList:
    # Function to initialize head
    def __init__(self):
       self.head = None
# Code execution starts here
if __name__=='__main__':
# Start with the empty list
    llist = LinkedList()
    llist.head = Node(1)
    second = Node(2)
    third = Node(3)
    llist.head.next = second
    second.next = third

adding methods to the class LinkedList would allow us an easier way to add and remove nodes, similar to JAVA and C#.

Popular programming patterns

Fast and Slow pointers

The Fast and Slow pointer approach, also known as the Hare & Tortoise algorithm, is a pointer algorithm that uses two pointers that move through the linked list at different speeds.

By moving at different speeds (say, in a cyclic linked list), the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.

In-place reversal of linked list

This pattern allows us to reverse one node at a time starting with one variable (current) pointing to the head of the linked list, and one variable (previous) will point to the previous node that you have processed.

In a lock-step manner, you will reverse the current node by pointing it to the previous before moving on to the next node. Also, you will update the variable “previous” to always point to the previous node that you have processed.

Conclusion

As we covered the definition of a Linked List its implementation in different languages and its most common coding patterns, keep in mind there are more data structures that help overcome different limitations that come with Linked Lists.
We will be talking about those in future articles, along with their implementations and the most common coding patterns that help resolve their specific problems.

Stay tuned…