A linked list is a data structure that is basically a chain of nodes in which each node is connected to each other by means of pointers or references. It is dynamic in nature; that means that the size of the linked list can vary depending on the requirements of the users. It is a collection of similar kinds of items. The basic building block of linked list is a node.
Node
Node is a basic building block of linked list that is comprised of two parts, a data and a next pointer. The data part basically contains the data whereas the next pointer contains the reference to the next node. The last node in the linked list points to null. The first node in the linked list is called the Head node and last node is called the Tail node.
![Linked List]()
A linked list must provide the following operations:
- Add nodes
- Remove nodes
- Iterate among nodes
- Find nodes
Node Chaining
For creating a linked list we must understand what a node is and how node chaining is done. Node is a basic building block of a linked list that must consist of two things, one is data and the other is a pointer to the next node. Since we are not using pointers in C# we will store the reference of the next node. So our node class will look like:
class Node
{
public int Value { get; set; }
public Node Next { get; set; }
}
In this class the Value property is used for holding data of the type integer and the Node property is used for holding the reference of the next node.If we want to create nodes we will create them like:
Node firstnode = new Node { Value = 3 };
The preceding line will create a node with Value 3 that is pointing to null.
Node secondnode = new Node { Value = 5 };
Now we have created a second node that has the value 5 and it also points to null. In order to create a link between the two we will update the Next property of the first node to the second node.
firstnode.Next = secondnode;
Similarly I am creating the third node that points to the second node.
Node thirdnode = new Node { Value = 7 };
secondnode.Next = thirdnode;
Now we have the following structure: 3-> 5-> 7. For iterating among the nodes we will write the following code:
while (node != null)
{
Console.WriteLine(node.Value);
node = node.Next;
}
I hope the concept of node and node chaining is clear from the example above. Now we will start creating the dynamic Linked List class.
In order to make a dynamic linked list we will implement generics so that it can hold any type of data. So we will first create a generic node class whose code is given below:
public class LinkedListNode<T>
{
public LinkedListNode(T value)
{
Value = value;
}
public T Value { get; set; }
public LinkedListNode<T> Next { get; set; }
}
It is similar to the preceding node class except it implements generics and it has a constructor for setting the value of a node.
Now we will start with the Linked List class. A Linked List must contain a Head and a Tail node where the Head node always points to the first node in the list and the Tail node indicates the last node of the list. The Tail node will always point to null that indicates the end of the list. I am implementing an ICollection interface for implementing the linked list.
Our linked list class will look like:
public class LinkedList<T> : ICollection<T>
{
public LinkedListNode<T> Head
{
get;
private set;
}
public LinkedListNode<T> Tail
{
get;
private set;
}
}
Note: We always need to maintain a Head and a Tail node in the Linked List.
Now we will build our linked list class and will add methods to that. I am explaining the functionality of each method. The code for the linked list is also attached to this article.
Adding Nodes in Linked List
For adding nodes in the list I am using three methods AddFirst, AddLast and Add. The Add method is configured to call the AddFirst method by default.
Add First
When adding a node to the start of the list we need to take care of the following things:
- If the node to be added is the first node in the list then the Tail node and Head node will be the same.
- If a node to be added to the list is not the first node then we need to store the head node in a temporary variable and set the Head node to the newly added node and update its next pointer to the temporary node (that was the Head node initially). In this way our newly added node becomes the Head node and it starts pointing to the older Head node that has become the second node in the list.
public void AddFirst(LinkedListNode<T> node)
{
LinkedListNode<T> temp = Head;
Head = node;
Head.Next = temp;
Count++;
if (Count == 1)
{
Tail = Head;
}
}
Note: For checking the node count we will always check and maintain the count property of a class.
Internally there is one more method with the same name in which we pass the generic value as the parameter. Practically we will call this method with our value that further calls the preceding method by passing the LinkedListNode.
public void AddFirst(T node)
{
AddFirst(new LinkedListNode<T>(node));
}
Add Last
This method is used to add the node at the end of the list. It is similar to the AddFirst method except we update the Tail node here instead of Head Node.
- If there is no node in the list then the Head node and Tail node will be the same.
- If we have one or more nodes then we will store the Tail node in some temporary variable and set the Tail node to the newly added node and we will update the next pointer of our temporary node to the Tail node.
public void AddLast(LinkedListNode<T> node)
{
if (Count == 0)
{
Head = node;
}
else
{
Tail.Next = node;
}
Tail = node;
Count++;
}
Like AddFirst we have the AddLast method that accepts the generic value and internally calls the preceding AddLast method by passing a LinkedListNode.
public void AddLast(T node)
{
AddLast(new LinkedListNode<T>(node));
}
Add Method
This method comes with an ICollection interface and it is internally calling the Add First method for adding the node at the front of the list.
public void Add(T item)
{
AddFirst(item);
}
Note: We should always increment the Count property when adding the node to the list.
Removing Nodes from Linked List
For removing nodes from the list we have three methods RemoveFirst, RemoveLast and Remove.
Remove First
For removing the first element in the list we must have the following points in mind:
- List count should not be zero.
- If there is only one element in the list then the Head and Tail node must be set to null or we can also call the Clear method since there is no element in the list.
- If there is more than one node in the list then we need to set the Head node to the next pointer of the Head node (that is the second node). By doing that the second element in the list becomes the Head node.
public void RemoveFirst()
{
if (Count <= 1)
{
Clear();
}
else
{
LinkedListNode<T> current = Head;
Head = current.Next;
if (Count == 1)
{
Head = null;
Tail = null;
}
Count--;
}
}
Remove Last
For removing the last element in the list we must check the following:
- List count should not be zero.
- If there is only one element in the list then the Head and Tail nodes must be set to null or we can also call the Clear method since there is no element in the list.
- If there is more than one node in the list then we need to iterate among all the nodes and need to retain the previous node (because this node is going to become the Tail node). While iterating among all the nodes we need to find the node whose next pointer is null because that node is the Tail node. Since we are also maintaining the previous node we will also change its next pointer to null and set the Tail node to the previous node.
public void RemoveLast()
{
if (Count <= 1)
{
Clear();
}
else
{
LinkedListNode<T> previous = null;
LinkedListNode<T> current = Head;
while (current != null)
{
if (current.Next == null)
{
Tail = previous;
Tail.Next = null;
}
previous = current;
current = current.Next;
}
Count--;
}
}
Remove with Value
For removing a specific node in the list we need to iterate among all the nodes and also need to retain the previous node because if we are removing the node between the list then we need to change the linking of the previous node and change its next pointer to the current node's next value. We need to take care of the following conditions:
- If the node that we want to delete is the first node in the list (because its previous node will be null) then we will call the Remove First method to remove the first node of the list.
- If the node that we want to delete is the last node in the list then we need to set the previous node's next pointer to null.
- The node that we want to delete is between the list then when we get the matched node then we need to point to its previous node's next pointer to the current node's next pointer.
public bool Remove(T item)
{
LinkedListNode<T> previous = null;
LinkedListNode<T> current = Head;
while (current != null)
{
if (current.Value.Equals(item))
{
if (previous != null)
{
previous.Next = current.Next;
if (current.Next == null)
{
Tail = previous;
}
Count--;
}
else
{
RemoveFirst();
}
}
previous = current;
current = current.Next;
}
return false;
}
Note: We should always decrement the Count property on removing the node from the list.
ICollection Interface Methods
Clear Property
It is used for clearing the linked list. In order to clear the linked list we will set the Head and Tail node to null and will set the Count to 0 that indicates that no items are there in the list.
public void Clear()
{
Head = null;
Tail = null;
Count = 0;
}
Contains Method
This method will iterate among all the nodes in the list and check whetehr or not our passed value matches with any node in the list.
public bool Contains(T item)
{
LinkedListNode<T> current = Head;
while (current != null)
{
if (current.Value.Equals(item))
{
return true;
}
current = current.Next;
}
return false;
}
Copy To Method
This method will copy all the nodes of the linked list into the array.
public void CopyTo(T[] array, int arrayIndex)
{
LinkedListNode<T> current = Head;
while (current != null)
{
array[arrayIndex++] = current.Value;
current = current.Next;
}
}
Count Property
This property is used for maintaining the count of nodes in the list. This count property is incremented in every Add method and is decremented with every remove method. Its set accessor is made private so that it should not be set outside the list class.
public int Count
{
get;
private set;
}
IsReadonly Property
The IsReadonly property is set to false and I am not exactly using it in this example.
public bool IsReadOnly
{
get { return false; }
}
GetEnumerator Method
If we want to use a foreach loop with our class then we need to implement the IEnumerable interface. The ICollection interface is inherited from IEnumerable and the IEnumerable<T> interface is due to which we need to implement two GetEnumerators methods, one regular one and another generic one.
public IEnumerator<T> GetEnumerator()
{
LinkedListNode<T> current = Head;
while (current != null)
{
yield return current.Value;
current = current.Next;
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return ((System.Collections.Generic.IEnumerable<T>)this).GetEnumerator();
}
Advantages of Linked List
- The size of a linked list can change at run time.
- Insertion and deletion operations in a linked list are flexible. Like for arrays we don't need to shift the nodes, we just need to update the next pointer.
- Memory is allocated and de-allocated dynamically. We don't need to bother about that.
- Using a linked list we can easily implement other data structures like stack, queue and so on.
Disadvantages of Linked List
- A Linked List is sequential. Accessing an item in a linked list needs iteration among all the nodes of the list that makes the retrieval process heavy.
- Extra memory is required to store the next pointer that is an overhead for a Linked List.