July 15, 2018

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.
graph LR;
w-->x;
x-->y;
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:

graph LR;
A["{w, x, y, z}"]
B["{w, y, z}"]
A--remove x-->B;


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; }

{
Value = value;
}

}


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 int count = 0;

public int Count => count;

{
if (count == 0)
{
}
else
{
// put the new head in place.

// move the references around to reflect the sequence
newNode.Previous = tail;
}

//set end pointers

count++;
}

{
if (count == 0)
{
}
else
{
var previousTail = tail;
tail = newNode;

// make nodes reference each other
previousTail.Next = tail;
tail.Previous = previousTail;
}

//set end pointers

count++;
}

{
if (this.count == 0)
{
return;
}

{
}
else
{
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;
}

{
// the node given was not in this list so we will do nothing
return;
}

node = node.Next;
}

count++;
}
}

{
if (this.count == 0)
{
return;
}

if (existingNode == tail)
{
}
else
{
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;
}

{
// the node given was not in this list so we will do nothing
return;
}

node = node.Next;
}

count++;
}
}

{
var leftNode = node.Previous;
var rightNode = node.Next;

// point surrounding nodes to each other
leftNode.Next = rightNode;
rightNode.Previous = leftNode;

{
}
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]
{

}

[Fact]
{

}

[Fact]
{

}

[Fact]
{

}

[Fact]
{

}

[Fact]
{

}

[Fact]
{

}

[Fact]
public void Can_Remove_Tail()
{

}

[Fact]
public void Can_Remove_Middle_Node()
{

}
}

Updated on

Effective Microservices

I recently gave a talk at the Orlando Backend Devs Meetup on Effective Microservices. Here is the video:[Here are the slides](https://ww...… Continue reading

Software Interfaces in the Wild

Published on October 28, 2018

Microservices are not Micro; They are Vertical

Published on October 16, 2018