Kubernet

Linked Lists

Justin VanWinkle -

Linked lists are primarily used when data access is desired to be sequential in nature.  This means accessing y will always come after x.

There are many types of linked lists, but for our sake, we will stick  with the most common implementations which are singly linked lists and  doubly linked lists.

A linked list contains nodes which house a single element of data and  reference to the next node.  In the case of a doubly linked list, the  node will also contain a reference to the previous node.

Best uses

Consider the following set: {w, x, y, z}.  A linked list is the ideal data structure for representing this set if the following conditions are true:

  • Access to each element is not necessary unless the preceding has been accessed.
w
x
y
z

Access to the set is intended to begin only from the beginning (w) or end (z).

Adding and/or removing elements will be necessary. $$ Removing an element in the middle:

remove x
{w, x, y, z}
{w, y, z}

Big-O

Space Complexity

For each element of data, a single node is created.  This means that  the standard linked list implementation will have a space complexity of O(n)

.

Time Complexity

Access: O(n)

Search: O(n)

Insert: O(1)

Delete: O(1)

While insert and delete are constant time, the location of the insert  or delete needs to be found.  So if the majority of intended actions  consist of insertion or deletion, keep this in mind as performance might  not be as good as intended.

Implementation

This is a doubly-linked list with basic functionality and no external dependencies.

Nodes

First, let’s consider the individual nodes that make up the linked list.  Each node has three properties:

  1. A generically typed Value field that holds arbitrary data.
  2. A reference to the Next
  3. A reference to the Previous node.
public class DoubleLinkedListNode<T>
{
    public T Value { get; set; }
    public DoubleLinkedListNode<T> Next { get; set; }
    public DoubleLinkedListNode<T> Previous { get; set; }
    
    public DoubleLinkedListNode(T value)
    {
        Value = value;
    }
    
}

Double Linked List

The linked list class contains three fields:

  1. head tracks the first node in the list
  2. tail tracks the last node in the list
  3. count tracks the total numer of nodes in the list

Three properties on the Linked List encapsulate each of the three fields to prevent them from being set externally.

The actions that exist on the list are:

  1. AddFirst - adds a node to the beginning of the list.
  2. AddLast - adds a node to the end of the list.
  3. AddAfter - adds a node after the specified node.
  4. AddBefore - adds a node before the specified node.
  5. Remove - removes the specified node from the list.
public class DoubleLinkedList<T>
{
    internal DoubleLinkedListNode<T> head;
    internal DoubleLinkedListNode<T> tail;
    internal int count = 0;

    public DoubleLinkedListNode<T> First => head;
    public DoubleLinkedListNode<T> Last => tail;
    public int Count => count;

    public void AddFirst(DoubleLinkedListNode<T> newNode)
    {            
        if (count == 0)
        {
            head = newNode;
            tail = head;
            head.Next = tail;
            tail.Previous = head;
        }
        else
        {
            // put the new head in place.
            var previousHead = head;
            head = newNode;
            
            // move the references around to reflect the sequence
            newNode.Next = previousHead;
            newNode.Previous = tail;
            previousHead.Previous = newNode;
        }

        //set end pointers
        head.Previous = tail;
        tail.Next = head;
        
        count++;
    }

    public void AddLast(DoubleLinkedListNode<T> newNode)
    {
        if (count == 0)
        {
            head = newNode;
            tail = head;
            head.Next = tail;
            tail.Previous = head;
        }
        else
        {
            var previousTail = tail;
            tail = newNode;
            
            // make nodes reference each other
            previousTail.Next = tail;
            tail.Previous = previousTail;
        }

        //set end pointers
        head.Previous = tail;
        tail.Next = head;

        count++;
    }

    public void AddBefore(DoubleLinkedListNode<T> existingNode, DoubleLinkedListNode<T> newNode)
    {
        if (this.count == 0)
        {
            return;
        }
        
        if (existingNode == head)
        {
            AddFirst(newNode);
        }
        else
        {
            var node = head;
            while (true)
            {
                if (node == existingNode)
                {
                    // existing node found
                    var rightNode = existingNode;
                    var leftNode = existingNode.Previous;

                    // point surrounding nodes to new node
                    leftNode.Next = newNode;
                    rightNode.Previous = newNode;

                    // point new node to surrounding nodes
                    newNode.Next = rightNode;
                    newNode.Previous = leftNode;
                   
                    break;
                }

                if (node.Next == head)
                {
                    // the node given was not in this list so we will do nothing
                    return;
                }
                
                node = node.Next;
            }

            count++;
        }
    }
    
    public void AddAfter(DoubleLinkedListNode<T> existingNode, DoubleLinkedListNode<T> newNode)
    {
        if (this.count == 0)
        {
            return;
        }
        
        if (existingNode == tail)
        {
            AddLast(newNode);
        }
        else
        {
            var node = head;
            while (true)
            {
                
                if (node == existingNode)
                {
                    // existing node found.
                    var rightNode = existingNode.Next;
                    var leftNode = existingNode;
                    
                    // point surrounding nodes to new node
                    rightNode.Previous = newNode;
                    leftNode.Next = newNode;

                    // point new node to surrounding nodes
                    newNode.Previous = leftNode;
                    newNode.Next = rightNode;
                   
                    break;
                }

                if (node.Next == head)
                {
                    // the node given was not in this list so we will do nothing
                    return;
                }

                node = node.Next;
            }

            count++;
        }            
    }

    public void Remove(DoubleLinkedListNode<T> node)
    {
        var leftNode = node.Previous;
        var rightNode = node.Next;

        // point surrounding nodes to each other
        leftNode.Next = rightNode;
        rightNode.Previous = leftNode;
        
        if (node == head)
        {
            head = rightNode;
        }
        else if (node == tail)
        {
            tail = leftNode;
        }

        count--;            
    }
}

Tests

While not polished, these tests can give some insight into how the linked list behaves in specific scenarios.

public class LinkedLists
{
    [Fact]
    public void Add_First_Count_0()
    {
        var linkedList = new DoubleLinkedList<int>();
        var node = new DoubleLinkedListNode<int>(1);

        linkedList.AddFirst(node);

        linkedList.Count.Should().Be(1);
        linkedList.First.Should().Be(node);
        linkedList.First.Value.Should().Be(1);
        linkedList.Last.Should().Be(node);
        linkedList.Last.Value.Should().Be(1);
    }
    
    [Fact]
    public void Add_Last_Count_0()
    {
        var linkedList = new DoubleLinkedList<int>();
        var node = new DoubleLinkedListNode<int>(1);

        linkedList.AddLast(node);
        
        linkedList.Count.Should().Be(1);
        linkedList.First.Should().Be(node);
        linkedList.First.Value.Should().Be(1);
        linkedList.Last.Should().Be(node);
        linkedList.Last.Value.Should().Be(1);
    }
    
    [Fact]
    public void Add_Before_Count_0_Does_Not_Add()
    {
        var linkedList = new DoubleLinkedList<int>();
        var newNode = new DoubleLinkedListNode<int>(1);
        var nodeNotInList = new DoubleLinkedListNode<int>(2);

        linkedList.AddBefore(nodeNotInList, newNode);
        
        linkedList.Count.Should().Be(0);
    }
    
    [Fact]
    public void Add_After_Count_0_Does_Not_Add()
    {
        var linkedList = new DoubleLinkedList<int>();
        var newNode = new DoubleLinkedListNode<int>(1);
        var nodeNotInList = new DoubleLinkedListNode<int>(2);

        linkedList.AddAfter(nodeNotInList, newNode);
        
        linkedList.Count.Should().Be(0);
    }
    
    [Fact]
    public void Can_Add_After_Element()
    {
        var linkedList = new DoubleLinkedList<int>();
        var node1 = new DoubleLinkedListNode<int>(1);
        var node2 = new DoubleLinkedListNode<int>(2);
        var newNode = new DoubleLinkedListNode<int>(3);

        linkedList.AddFirst(node1);
        linkedList.AddLast(node2);
        linkedList.AddAfter(node1, newNode);
        
        linkedList.Count.Should().Be(3);
        linkedList.First.Should().Be(node1);
        linkedList.Last.Should().Be(node2);

        linkedList.First.Value.Should().Be(1);
        linkedList.First.Next.Value.Should().Be(3);
        linkedList.Last.Value.Should().Be(2);
        linkedList.Last.Previous.Value.Should().Be(3);
    }

    [Fact]
    public void Can_Add_Before_Element()
    {
        var linkedList = new DoubleLinkedList<int>();
        var node1 = new DoubleLinkedListNode<int>(1);
        var node2 = new DoubleLinkedListNode<int>(2);
        var newNode = new DoubleLinkedListNode<int>(3);

        linkedList.AddFirst(node1);
        linkedList.AddLast(node2);
        linkedList.AddBefore(node2, newNode);
        
        linkedList.Count.Should().Be(3);
        linkedList.First.Should().Be(node1);
        linkedList.Last.Should().Be(node2);

        linkedList.First.Value.Should().Be(1);
        linkedList.First.Next.Value.Should().Be(3);
        linkedList.Last.Value.Should().Be(2);
        linkedList.Last.Previous.Value.Should().Be(3);
    }

    [Fact]
    public void Can_Remove_Head()
    {
        var linkedList = new DoubleLinkedList<int>();

        var node1 = new DoubleLinkedListNode<int>(1);
        var node2 = new DoubleLinkedListNode<int>(2);
        var node3 = new DoubleLinkedListNode<int>(3);

        linkedList.AddFirst(node1);
        linkedList.AddLast(node2);
        linkedList.AddLast(node3);
        
        linkedList.Remove(linkedList.First);
        
        linkedList.Count.Should().Be(2);
        linkedList.First.Should().Be(node2);
        linkedList.Last.Should().Be(node3);
     
        linkedList.First.Next.Should().Be(node3);
        linkedList.First.Previous.Should().Be(node3);
        linkedList.Last.Previous.Should().Be(node2);
        linkedList.Last.Next.Should().Be(node2);

    }

    [Fact]
    public void Can_Remove_Tail()
    {
        var linkedList = new DoubleLinkedList<int>();

        var node1 = new DoubleLinkedListNode<int>(1);
        var node2 = new DoubleLinkedListNode<int>(2);
        var node3 = new DoubleLinkedListNode<int>(3);

        linkedList.AddFirst(node1);
        linkedList.AddLast(node2);
        linkedList.AddLast(node3);
        
        linkedList.Remove(node3);
        
        linkedList.Count.Should().Be(2);
        linkedList.First.Should().Be(node1);
        linkedList.Last.Should().Be(node2);
        
        linkedList.First.Next.Should().Be(node2);
        linkedList.First.Previous.Should().Be(node2);
        linkedList.Last.Previous.Should().Be(node1);
        linkedList.Last.Next.Should().Be(node1);
    }

    [Fact]
    public void Can_Remove_Middle_Node()
    {
        var linkedList = new DoubleLinkedList<int>();

        var node1 = new DoubleLinkedListNode<int>(1);
        var node2 = new DoubleLinkedListNode<int>(2);
        var node3 = new DoubleLinkedListNode<int>(3);

        linkedList.AddFirst(node1);
        linkedList.AddLast(node2);
        linkedList.AddLast(node3);
        
        linkedList.Remove(node2);
        
        linkedList.Count.Should().Be(2);
        linkedList.First.Should().Be(node1);
        linkedList.Last.Should().Be(node3);
        
        linkedList.First.Next.Should().Be(node3);
        linkedList.First.Previous.Should().Be(node3);
        linkedList.Last.Previous.Should().Be(node1);
        linkedList.Last.Next.Should().Be(node1);
    }
}