Introduction to the Linked List Data Structure and Implementation

Loading…

The linked list data structure is one of the fundamental data structures in computer science.

Think of the linked list data structure as your ABCs. Without learning the ABCs, it is difficult to conceptualize words, which are made up by stringing alphabetical characters together.

Therefore, you want to know the ins and outs of the linked list data structures.

In this article, we will explore the linked list data structure’s key features and operations. Afterwards, we will begin by implementing our own singly linked list.

Another separate post will be dedicated towards the doubly linked list, which is a variant of the linked list data structure.

I will be proceeding on with the assumption that you know what a data structure is. If not, I recommend first getting acquainted with data structures before proceeding.

Why Should I Learn about the Linked List Data Structure?

Learning the linked list data structure is like learning your ABCs. A solid understanding of your ABCs will enable you to smoothly transition into stringing these characters together to make words and sentences.

On the other hand, not learning the linked list data structure and skipping ahead is the same as trying to write a well-crafted thesis without knowing your ABCs.

If you skip learning the linked list data structure, you will have more difficulty conceptualizing and understanding other data structures such as the binary search tree.

If I convinced you to read on, prepare your minds and pens.

Afterwards, proceed onto the next section.

What is the Linked List Data Structure?

The linked list data structure contains a reference to a head and/or tail node. The head and tail node is the first and last node in the series of nodes.

In the linked list data structure, each node has a pointer to the next and/or previous node.

Those that have a pointer to both the next and previous node are known as the doubly linked list.

Linked lists that only have a single pointer pointing to the next or previous node (usually next node pointers are more common) are known as the singly linked list.

The linked list data structure is like a train. A train has many carriages. Each carriage is “linked” to the next carriage, until we get to the first or last carriage, where there is no “carriage”. Hence the name “linked list”.

If you try to go to the next carriage (please don’t try this in real life), you will fall onto the tracks and if the train is moving … let’s not go there.

linked-list-train

Real-world Examples of Linked Lists

Anyway, in Computer Science, as I mentioned previously, the first node is called the “head” and the last node is known as the “tail“.

Using the train illustration, the linked list data structure would be the train. The head and tail would be the first and last carriage respectively.

The carriages in this illustration are called “nodes“. These nodes store the data itself and a pointer to the next and/or previous node. As I explained before, the head is the first carriage that you see in the image above.

Another example of a real-world example of a linked is a simple photo slider with a forward and backward navigation button. There is a “next image” arrow button and another arrow that when clicked, takes users to the previous image. It has pointers to only the next and the previous image.

These examples above would all be examples of the doubly linked list.

There are many variations of the linked list, but the two most common types of linked lists are doubly linked lists and singly linked lists.

And honestly, once you have a strong grasp of how these two works, you can figure out how the other variations work with relative ease.

As an introduction to the linked list data structure, we will be working on implementing the singly linked list in this post.

In a future post, we will work on implementing the doubly linked list.

Singly Linked List vs Doubly Linked List

Both the examples above are examples of a doubly linked list.

To sum it up, a doubly linked list

  • Has a head and a tail.
  • Each node has the data that is being stored and two pointers pointing at the next and previous node.
  • The head backward pointer points to null.
  • The tail’s forward pointer points to null.

In contrast, a singly linked list

  • Has either a head and/or a tail depending on how you implement it.
  • Each node has the data that is being stored and only a single pointer pointing to the next or previous node.
  • The head or tail has a pointer pointing to null.

singly linked list versus doubly linked list

What are Other Key Components of the Linked List?

Linked lists are dynamic data structures.

Dynamic data structures have the flexibility to grow and shrink in size. Inserting data to the start and/or end of the list is very fast.

Static data structures, such as arrays, cannot grow during run time. In another word, let’s say you have five items in your array. You want to add an item to the array.

To do that, you will need to create a new array (this time, probably increasing the size from five to ten, in case more items are added in the future).

Afterwards, you will need to iterate through the old array and transfer the contents over to the new array. As you can see, this would take O(N).

O(N) is a form expressing time/memory complexity. In another word, it is a quantitative form of expressing how much time/memory an operation takes.

I recommend reading up on an Introduction to big O notation to get a basic understanding of how big O works before proceeding.

Big-O comparison – Linked List vs Arrays

Operation Linked List Arrays
Search O(N) O(1)
Insert at start O(1) O(N)
Insert at end O(N) O(1)

Creating the UML Diagram for the Singly Linked List

First, I will summarize the data that our singly linked list will have.

  • Head. This is the first node of the linked list.
  • (optional) is empty boolean flag – for keeping the state of the linked list.
  • (optional) size variable – for keeping track of the number of nodes in the linked list.

Since the head node is a custom class, we must determine what the node contains in a singly linked list.

Naturally, because nodes in a singly linked list has a pointer to the head node, we need to give it a pointer to the next node, right? Therefore, pointers in our linked list implementation will have the following data

  • Raw data.
  • Pointer to the next node.

Now, when programming, it is often best practice to program to an interface or a super type, so that on demand, we can dynamically change the way the List behaves at run-time. Sometimes, based on the case, the linked list might not be the best data structure for the job.

Programming to an interface gives us the flexibility of changing the implementation details at run time.

Below are some possible methods that we can have for our linked list implementation. At the very least, users should be able to add and remove data from the linked list, as well as view the data.

  • remove(int index): remove an item from the list by index.
  • remove(T data): remove an item from the list by value.
  • add(T data): add data to the list.
  • add(int index, T data): add data to a specific index in the list.
  • size(): Get the number of items in the linked list.
  • print(): Print all the items in the linked list.

singly linked list data structure uml diagram

Now that we have a basic idea of how our linked list works, we can now begin writing out the implementation details.

Your Implementation is Your Own Implementation

Before proceeding, I would like to take time and mention to you that how you implement the linked list data structure is entirely up to you, provided that your implementation meets the specifications of the linked list data structure.

However, there are good and bad implementations.

Perhaps you are familiar with the saying that code should be written not for machines to read, but for humans.

Good implementations should maintain a suitable balance between performance and readability.

The consumer of your linked list should be given ample enough functionality so that they can flexibly interact with the linked list.

Not having a simple size() method might make it difficult for them to keep track of how many items are currently in the linked list.

Creating the Linked List Node

First, we will have to build the linked list node, which will contain the data, as well as a pointer to the next node. If possible, we would like to have the Node accept a generic data type.

In C++ however, when working in a mission critical environment, it is often good to have a specific implementation for each data type, as C++ templates does incur a performance hit.

Alternatively, if the performance benefit is not necessary, we can accept the performance penalty and choose to go for the generic implementation.

For example, in Java, one way we can implement the Node is to have it extend the Comparable interface. Note that it is not necessary for your implementation to extend the Comparable interface.

We can create our own custom interface for comparing data (I.e. perform equality check), but OOP is not the topic we are focusing on in this tutorial, so we will be omitting that step.

Java

public class Node<T> {

    // The data
    private T data;
    // Pointer to the next node
    private Node<T> nextNode;

    public Node(T data) {
        this.data = data;
    }

    /*
     * =====================================
     * ======== Getters and Setters ========
     * =====================================
     * */
    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node<T> nextNode) {
        this.nextNode = nextNode;
    }

    // In most cases int is recommended to override the toString() method
    // so that the data will be converted into a string format
    // that is meaningful to the user
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

JavaScript

/**
 * Node is a wrapper around data
 * with a pointer to the next node
 *
 * @param data the data
 * @param {Node} nextNode
 * */
function Node(data, nextNode) {
    if (!(this instanceof Node)) {
        return new Node(data, nextNode);
    }
    this.data = data;
    this.nextNode = nextNode || null;
}

C++

// typedef struct to ensure that we don't have to do the following
// Node *nodePtr = ...
// Rather we can do the following
// node_ptr node
typedef struct Node
{
    int data;
    Node *nextNode;
} * node_ptr;

The List Abstract Data Type

By list interface, we are referring to the list abstract data type.

Now, remember that the purpose of the list interface is to ensure that we can change the implementation details of the list abstract data type at run time.

Now in dynamic languages such as JavaScript, you most likely won’t need to create super types, although you can achieve the same effect via prototypal inheritance.

In languages such as Java and C++ we, use inheritance to achieve this.

Remember that when defining the interface for the list, you are free to determine which methods to include. As the designer of the interface, when designing for real-world use, it is important to consider how the user will interact with the list.

Trying to include every single feature not only makes the code of sub-classes or modules implementing your interface a lot longer, having too many methods could also create confusion for the user.

Therefore, when deciding on methods, make sure that it is either essential or useful to the user.

Java

public interface List<T> {

    /**
     * Insert data to the end of the list.
     * @param data the data to add.
     * */
    void insert(T data);

    /**
     * Insert data after the node at a specific index.
     * @param data the data to add.
     * @param index the index of node after which we will add data.
     * */
    void insertAfter(T data, int index);

    /**
     * Search from the start of the list and find
     * data to remove.
     * @param data the data to remove.
     * */
    void remove(T data);

    /**
     * Remove the item at the nth index of the list.
     *
     * @param index
     * @throws IndexOutOfBoundsException
     * */
    void removeAt(int index) throws IndexOutOfBoundsException;

    /**
     * Print items inside of the list.
     * */
    void print();

    /**
     * Get the size of the list.
     * */
    int size();

}

JavaScript

/**
 * @param itemsToAdd either an item or a collection of items to add
 * @return this
 * */
LinkedList.prototype.add = function add(itemsToAdd) {
    if (Array.isArray(itemsToAdd)) {
        addBatch.call(this, itemsToAdd);
    } else {
        addSingle.call(this, itemsToAdd);
    }
    return this;
};

LinkedList.prototype.addByIndex = function addByIndex(itemsToAdd, index) {
    if (Array.isArray(itemsToAdd)) {
        addBatchAt.call(this, itemsToAdd, index);
    } else {
        addSingleAt.call(this, itemsToAdd, index);
    }
    return this;
};

/**
 * Remove item by equality check
 *
 * @param itemToRemove
 * @return this
 * */
LinkedList.prototype.remove = function remove(itemToRemove) {
    removeItem.call(this, itemToRemove);
    return this;
};

C++

class List
{
private: 
	// Make the Linked List Generic. 
	// We don't want to constantly have to type out "node *"
	// Instead we can just write node_ptr (instead of node *).
	// FYI the following is invalid ...
	// template <class T> 
	// typedef struct Node ... 
	typedef struct Node
	{
		int data;
		Node *nextNode;
	} * node_ptr;

	// The head node for the singly linked list.
	node_ptr head;

	// size_t is an unsigned integer type for those that don't know
	// It is the type when we do the following
	// sizeof(variableName);
	size_t sz;

	void IncrementSize();
	void DecrementSize();

public:
	List();
	// Copy Constructor
	List(const List& rhs);

	// Copy Constructor when called with equals.
	// Challenge to readers to implement this
	// List & operator = (const List& rhs);

	void Add(int data);
	bool Remove(int data);
	bool IsEmpty() const;

	void EmptyList();

	// size of linked list:
	size_t Size() const;

	void Traverse() const;
	~List();
};

Adding Data to the Singly Linked List Data Structure

In all types of lists, we should be able to add data to it.

The advantage of the linked list is the fact that the linked list is a dynamic data structure. Because we have a reference to the head, it takes O(1) to add data to the front of the linked list.

Now, when adding data to the front of the linked list, we have two cases.

  1. When the linked list is empty.
  2. When the linked list is not empty.

When we are adding the first item to the list, the head node is null, since the list is empty.

In this case, it is simple: set the newly created node as the head.

If the linked list is not empty, that means we have a head.

In this case, we do the following.

  1. Create the new node.
  2. Check if list is empty.
    • If the list is empty, set the new node as the new head.
    • If the list contains nodes, have the new head’s next node pointer point to the previous head. Afterwards, proceed to set the new node as the new head.

Here is an activity diagram that shows the entire process of adding an item to the front of the linked list.

singly linked list data structure add activity diagram

For the sake of completeness, let’s go through the insertion process again.

  1. Create new node: B.
  2. Set next node of B to A.
  3. Set the new head to B.linked list data structure add data

How do we check to see if the Linked List is empty?

In order for us to check whether the linked list is empty, we can employ the following methods.

  1. Check to see whether the head node is null.
  2. If you have a member variable that keeps track of the “size”, check if that equals zero.

 

Java

If this list is empty, it is simple. All we need to do is create a new Node with the data that is added. Afterwards, just simply set the head as the new Node that was created.

In the code below we can simplify the code inside of the if block to the following.

head = new Node<T>(data);

For the sake of emphasizing the fact that we are setting the head to the newNode, I added the extra line of code. Please bear in mind that the logic above is perfectly fine and is preferred in most cases.

if (this.isEmpty()) {
    Node<T> newNode = new Node<T>(data);
    head = newNode;
} else {
    addNodeAtStart(data);
}
incrementSize();

Below is the source code for adding the new data to the start of the linked list. In another word, making it the new head, when the list already contains data.

/**
 * Add data to the start of the linked list
 * */
private void addNodeAtStart(T dataToAdd) {
    Node<T> newHead = new Node<T>(dataToAdd);
    newHead.setNextNode(head);
    head = newHead;
}

JavaScript

/**
 * @param itemToAdd
 * @return this
 * */
LinkedList.prototype.add = function add(itemToAdd) {
    addSingle.call(this, itemsToAdd);
    return this;
};

Here, we are adding a single item to the linked list. As you can see, the only difference between adding the node and setting the data is the addition of a single step.

That is setting the next node pointer of the new head to point at the previous head.

/**
 * add a list of data into the linked list
 *
 * @this {LinkedList}
 * @param dataToAdd
 * */
var addSingle = function addSingle(dataToAdd) {
    checkDataType.call(this, dataToAdd);
    if (this.head == null) {
        this.head = new Node(dataToAdd);
    } else {
        // Set the new head to added data and next node to current head
        this.head = new Node(dataToAdd, this.head);
    }
    this.size++;
};

/**
 * add a list of data into the linked list
 *
 * @this {LinkedList}
 * @param {Array} list of items to be added
 * */
var addBatch = function addBatch(list) {
    for (var i = 0; i < list.length; i++) {
        addSingle.call(this, list[i]);
    }
};

C++

/**
 * \brief 
 * \param data The data to be added to the linked list
 */
void List::Add(int data)
{
	// Step 1.
	node_ptr newNodePtr = new Node;
	newNodePtr->data = data; 
	newNodePtr->nextNode = nullptr;			// Initialize all the fields
	
	// Step 2.
	if (IsEmpty())
	{
		this->head = newNodePtr;
	} 
	// Step 3.
	// List already contains a node. 
	// Therefore, add the node to the front of the linked list.
	else 
	{	
		node_ptr prevHeadPtr = this->head;	// Get reference to current head. 
		this->head = newNodePtr;			// Set newly inserted node to be the new head	
		newNodePtr->nextNode = prevHeadPtr; // Set new head to point to previous head
	}
	// Step 4.
	IncrementSize();
}

Removing Data from the Singly Linked List Data Structure

The other primary feature of the linked list data structure is to remove data from it. The operation can be summarized in the following steps.

As with the adding operation, the removal operation has two cases.

  1. Node to remove is the head node.
  2. Node to remove is not the head node.

Here is what the entire remove() operation looks like.

  1. Iterate through the list and find the data to remove.
  2. After finding the data, check whether data to remove is the head.
    • If it it the head, simply set the next node as the new head.
    • If it is not the head, have the previous node point to the node after the data the remove. In another words, previous node’s nextNode pointer should point at nextNode of data to remove.
  3. Remove the node.

singly linked list data structure remove activity diagram

Remove Head Node from the Linked List

This is simple:

  1. Get the next node to the head: B.
  2. Set B as the new head node.
  3. Remove the previous head node A.

Visually, the operation looks like this.

Visual illustration of removing head node from singly linked list

Removing a Node from the Linked List

Here, I am referring to a node that is not the head.

  1. Iterate through the linked list data structure.
  2. Find the node.
  3. Have available the previous node – A, and the next node (of the node to remove) – C.
  4. Link the previous node – A with the next node of the node to remove – C by updating the next node pointer of A.
  5. Lastly, remove the node to delete – B.

Diagram showing the removal process in singly linked list

 

Java

@Override
public void remove(T data) {

    if (isEmpty()) return;

    Node<T> currentNode = head;
    // We have found data to remove. It is the head
    if (currentNode.getData().compareTo(data) == 0) {
        removeHead();
    } else {
        // Look for the data to remove.
        remove(data, head, head.getNextNode());
    }
    decrementSize();
}

 

/**
 * Remove Data
 * */
private void remove(T data, Node<T> prevNode, Node<T> currentNode) {
    while (currentNode != null) {
        Node<T> nextNode = currentNode.getNextNode();
        if (currentNode.getData().compareTo(data) == 0) {
            // Found data to remove. Delete current data and link the next node with the previous node
            // If we are removing "B" from A, B, C We will go from
            // A --> B -- C -- null
            // to
            // A --> C --> null
            // A needs to change pointer reference from
            // B to point at C
            prevNode.setNextNode(nextNode); // update pointer reference
            currentNode = null;             // set current node to null to remove it
            return;                         // Break out of the loop
        }
        // update the references for the next iteration
        prevNode = currentNode;
        currentNode = nextNode;
    }
}

JavaScript

/**
 * Remove item if the item is deemed equal by
 * linked list equality check standards
 *
 * @this {LinkedList}
 * @param itemToRemove
 * */
var removeItem = function removeItem(itemToRemove) {
    var currentNode = this.head, prevNode = null;
    while (currentNode != null) {

        console.log("comparing: " + currentNode.data + " and " + itemToRemove);

        if (currentNode.data === itemToRemove) {
            console.log("Found item to remove");
            // If we are removing the head
            if (prevNode == null) {
                console.log("removing head");
                // set head to next node
                this.head = currentNode.nextNode;
            } else {
                // Update references
                var tempNextNode = currentNode.nextNode;
                currentNode = prevNode;
                currentNode.nextNode = tempNextNode;
            }
            this.size--;
            return this;
        }

        // Update pointers and traverse again
        prevNode = currentNode;
        currentNode = currentNode.nextNode;
    }
    console.log("Cannot find item to remove ... boo!");
    return this;
};

C++

/**
 * \brief Look through the linked list O (log n) and find the data to remove.
 * \param data 
 * \return <code>true</code> if data exists and is removed from linked list
 * Otherwise, return <code>false</code>
 */
bool List::Remove(int data)
{
  // Point to the previous node. Used when joining nodes
  node_ptr prevNodePtr = nullptr;
  node_ptr currentNodePtr = head;

  if (IsEmpty())
  {
    return false;
  }
  while (currentNodePtr != nullptr)
  {
    // Found data to remove. Perform remove operation.
    if (data == currentNodePtr->data)
    {
      node_ptr nodeAfterCurrentPtr = currentNodePtr->nextNode;

      // Deleting head 
      if (prevNodePtr == nullptr)
      {
        // Set the node after current Ptr as new head
        this->head = nodeAfterCurrentPtr;
        // For demonstrational purposes
        std::cout << "Deleted HEAD node with value: "
          << data << "!" << std::endl;
      }
      // Deleting a node that is not the head. 
      else
      {
        // Set previous node to point at node after the one to delete
        prevNodePtr->nextNode = nodeAfterCurrentPtr;
        // For demonstrational purposes
        std::cout << "Deleted node with value: "
          << data << "!" << std::endl;
      }

      // Deallocate from heap memory.
      delete currentNodePtr;

      DecrementSize();

      return true;
    }
    // Set the previous node pointer now to current node.
    // So that when loop repeats, it will point to previous node.
    prevNodePtr = currentNodePtr;
    // Afterwards, currentNodePtr will move onto the next node.
    currentNodePtr = currentNodePtr->nextNode;
  }
  // Just for demonstrational purposes, log to users 
  // that item was not found in the list.
  std::cout << "Item: " << data
    << " was not found in the list ... " << std::endl;

  return false;
}

 

Linked List Data Structure Additional Methods

In this tutorial, we have gone through the essential add() and remove() method. If you are up for the challenge, here are some basic ideas on additional methods that you can add to your linked list.

  • get(index): Get the data at a given index.
  • add(collection, index): Add a collection/list of items at a specific index.
  • Implement a copy constructor that takes another list and converts it into a linked list.

For all the methods that involve passing in an index, be sure to do the appropriate validation and throw an error if the index range is out of bounds.

Implementing these methods should give you a good workout and solidify your working knowledge of the linked list data structure. Furthermore, it should also build you up to become a better programmer.

Final Source Code

Attached below are the source code for the linked list data structure. Now, remember that as long as your linked list fits the definition of a linked list (I.e. contains a head and/or tail node with nodes that point to previous and/or next element), it is entirely up to you on how to actually implement the linked list data structure.

Well, that is the end of this tutorial. If this tutorial helped you understand the linked list data structure, please share this post so that other people can benefit from it as well.

As always, if there are any parts of the tutorial that could use some improvement, please leave a comment and let me know. I will do my best to follow up and amend any deficiencies.

Thank you for reading! And if you want to view the source code on GitHub, here are the links.

– Jay

Loading…

About the Author Jay

I am a programmer currently living in Seoul, South Korea. I created this blog as an outlet to express what I know / have been learning in text form for retaining knowledge and also to hopefully help the wider community. I am passionate about data structures and algorithms. The back-end and databases is where my heart is at.

follow me on: