Linked lists are a data structure that is made up of a series of nodes that are linked together. Each node contains a value and a pointer to the next node in the list. Linked lists are a great way to store data in an organized manner and can be used to implement stacks, queues, and other data structures. In this article, we will be discussing linked lists in detail, including how to implement them using classes, singly linked lists, doubly linked lists, traversing linked lists, inserting and deleting elements from linked lists, and skip lists.
Implementing Linked Lists Using Classes
In order to implement a linked list in C#, we must first create a class to represent a node in the list. The following class contains a node constructor that takes a value as a parameter and sets the Value property to the value passed in. The Next property is set to null, which indicates that the node is the last node in the list:
public class Node
{
public int Value { get; set; }
public Node Next { get; set; }
public Node(int value)
{
Value = value;
Next = null;
}
}Now that we have a class for the nodes, we can create a class for the linked list itself. This class will contain a constructor, which will take the head node of the list as a parameter. The head node is the first node in the list and is used to keep track of the list. The following class also contains methods for adding nodes to the list, removing nodes from the list, and traversing the list:
public class LinkedList
{
public Node Head { get; set; }
public LinkedList(Node head)
{
Head = head;
}
// Adds a node to the beginning of the list
public void AddNode(Node node)
{
node.Next = Head;
Head = node;
}
// Removes a node from the list
public void RemoveNode(Node node)
{
if(Head == node)
{
Head = Head.Next;
return;
}
Node current = Head;
while(current.Next != null)
{
if(current.Next == node)
{
current.Next = current.Next.Next;
return;
}
current = current.Next;
}
}
// Traverses the list, printing each node's value
public void TraverseList()
{
Node current = Head;
while (current != null)
{
Console.WriteLine(current.Value);
current = current.Next;
}
}
}Singly Linked Lists
Singly linked lists are a type of linked list in which each node contains a value and a pointer to the next node in the list. They are a great way to store data in an ordered manner. In addition, they are easy to implement using classes, as we have seen above.
When traversing a singly linked list, it is important to keep track of the current node and the previous node. This is because the only way to traverse a singly linked list is to start at the head node and follow the pointers from one node to the next until the end of the list is reached.
Doubly Linked Lists
Doubly linked lists are similar to singly linked lists, but they contain an additional pointer that points to the previous node in the list. This allows us to traverse the list in both directions. In addition, it makes it easier to insert and delete nodes in the list.
When implementing a doubly linked list, we must create a class for the nodes that contains two pointers, one that points to the next node and one that points to the previous node. The following class contains a node constructor that takes a value as a parameter and sets the Value property to the value passed in. The Previous and Next properties are set to null, which indicates that the node is the last node in the list:
public class Node
{
public int Value { get; set; }
public Node Previous { get; set; }
public Node Next { get; set; }
public Node(int value)
{
Value = value;
Previous = null;
Next = null;
}
}Next, we need to create a class for the doubly linked list itself. This class will contain a constructor, which will take the head node of the list as a parameter. The head node is the first node in the list and is used to keep track of the list. The following class also contains methods for adding nodes to the list, removing nodes from the list, and traversing the list:
public class DoublyLinkedList
{
public Node Head { get; set; }
public DoublyLinkedList(Node head)
{
Head = head;
}
// Adds a node to the beginning of the list
public void AddNode(Node node)
{
node.Next = Head;
Head.Previous = node;
Head = node;
}
// Removes a node from the list
public void RemoveNode(Node node)
{
if(Head == node)
{
Head = Head.Next;
Head.Previous = null;
return;
}
Node current = Head;
while(current.Next != null)
{
if(current.Next == node)
{
current.Next = current.Next.Next;
current.Next.Previous = current;
return;
}
current = current.Next;
}
}
// Traverses the list, printing each node's value
public void TraverseListForward()
{
Node current = Head;
while (current != null)
{
Console.WriteLine(current.Value);
current = current.Next;
}
}
// Traverses the list backwards, printing each node's value
public void TraverseListBackward()
{
Node current = Head;
while (current.Next != null)
{
current = current.Next;
}
while (current != null)
{
Console.WriteLine(current.Value);
current = current.Previous;
}
}
}Traversing Linked Lists
As we have seen above, traversing linked lists is a simple process that involves starting at the head node and following the pointers from one node to the next until the end of the list is reached. With singly linked lists, it is important to keep track of the current node and the previous node. This is not necessary with doubly linked lists, as they allow us to traverse the list in both directions.
Inserting and Deleting Elements from Linked Lists
Inserting and deleting elements from linked lists is a relatively straightforward process. In order to insert a new node into a list, we must first create the node and then set its Next property to point to the node that is currently at the front of the list. Then, we must set the Next property of the node at the front of the list to point to the new node.
When deleting a node from a list, we must first check if the node is the head node. If it is, then we must set the head node to point to the node that is currently next in the list. If it is not the head node, then we must traverse the list until we find the node that we want to delete and then set the Next property of the node before it to point to the node after it.
Skip Lists
A skip list is a type of linked list in which each node contains a value and one or more pointers that point to other nodes in the list. This allows us to skip over certain nodes when traversing the list, which makes the search process more efficient. Skip lists are often used to implement data structures such as dictionaries, sets, and maps.
When implementing a skip list, we must create a class for the nodes that contains an array of pointers and a value. The following class contains a node constructor that takes a value and an array of pointers as parameters and sets the Value and Pointers properties to the values passed in:
public class Node
{
public int Value { get; set; }
public Node[] Pointers { get; set; }
public Node(int value, Node[] pointers)
{
Value = value;
Pointers = pointers;
}
}
Next, we need to create a class for the skip list itself. This class will contain a constructor, which will take the head node of the list as a parameter. The head node is the first node in the list and is used to keep track of the list. The following class also contains methods for adding nodes to the list, removing nodes from the list, and traversing the list:
public class SkipList
{
public Node Head { get; set; }
public SkipList(Node head)
{
Head = head;
}
// Adds a node to the beginning of the list
public void AddNode(Node node)
{
Node current = Head;
for(int i = 0; i < node.Pointers.Length; i++)
{
if(current.Pointers[i] == null)
{
current.Pointers[i] = node;
node.Pointers[i] = null;
}
else
{
Node temp = current.Pointers[i];
current.Pointers[i] = node;
node.Pointers[i] = temp;
}
current = current.Pointers[i];
}
}
// Removes a node from the list
public void RemoveNode(Node node)
{
if(Head == node)
{
Head = Head.Pointers[0];
return;
}
Node current = Head;
while(current.Pointers[0] != null)
{
if(current.Pointers[0] == node)
{
for(int i = 0; i < node.Pointers.Length; i++)
{
current.Pointers[i] = node.Pointers[i];
}
return;
}
current = current.Pointers[0];
}
}
// Traverses the list, printing each node's value
public void TraverseList()
{
Node current = Head;
while (current != null)
{
Console.WriteLine(current.Value);
current = current.Pointers[0];
}
}
}Conclusion
In this article, we have discussed linked lists in detail, including how to implement them using classes, singly linked lists, doubly linked lists, traversing linked lists, inserting and deleting elements from linked lists, and skip lists. We have also seen how to implement each of these data structures in C#. Linked lists are a great way to store data in an organized manner and can be used to implement stacks, queues, and other data structures.
Exercises
Write a C# program to create a new singly linked list.
using System;
public class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
public class LinkedList
{
public Node head;
public LinkedList()
{
head = null;
}
public void Add(int data)
{
Node newNode = new Node(data);
if (head == null)
head = newNode;
else
{
Node current = head;
while (current.next != null)
{
current = current.next;
}
current.next = newNode;
}
}
}
public class Program
{
public static void Main()
{
LinkedList ll = new LinkedList();
ll.Add(10);
ll.Add(20);
ll.Add(30);
}
}Write a C# program to traverse a singly linked list.
using System;
public class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
public class LinkedList
{
public Node head;
public LinkedList()
{
head = null;
}
public void Add(int data)
{
Node newNode = new Node(data);
if (head == null)
head = newNode;
else
{
Node current = head;
while (current.next != null)
{
current = current.next;
}
current.next = newNode;
}
}
public void Traverse()
{
Node current = head;
while (current != null)
{
Console.Write(current.data + " ");
current = current.next;
}
}
}
public class Program
{
public static void Main()
{
LinkedList ll = new LinkedList();
ll.Add(10);
ll.Add(20);
ll.Add(30);
ll.Traverse();
}
}Write a C# program to insert an element into a doubly linked list.
using System;
public class Node
{
public int data;
public Node next;
public Node prev;
public Node(int data)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
public class LinkedList
{
public Node head;
public LinkedList()
{
head = null;
}
public void Add(int data)
{
Node newNode = new Node(data);
if (head == null)
head = newNode;
else
{
Node current = head;
while (current.next != null)
{
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}
}
public void Insert(int data, int index)
{
Node newNode = new Node(data);
if(head == null)
{
head = newNode;
return;
}
if(index == 0)
{
head.prev = newNode;
newNode.next = head;
head = newNode;
return;
}
Node current = head;
int i = 0;
while (current.next != null && i < index - 1)
{
current = current.next;
i++;
}
newNode.next = current.next;
newNode.prev = current;
if (current.next != null)
current.next.prev = newNode;
current.next = newNode;
}
}
public class Program
{
public static void Main()
{
LinkedList ll = new LinkedList();
ll.Add(10);
ll.Add(20);
ll.Add(30);
ll.Insert(25, 2);
}
}Write a C# program to delete an element from a doubly linked list.
using System;
public class Node
{
public int data;
public Node next;
public Node prev;
public Node(int data)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
public class LinkedList
{
public Node head;
public LinkedList()
{
head = null;
}
public void Add(int data)
{
Node newNode = new Node(data);
if (head == null)
head = newNode;
else
{
Node current = head;
while (current.next != null)
{
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}
}
public void Delete(int index)
{
if (head == null)
return;
if (index == 0)
{
head = head.next;
head.prev = null;
return;
}
Node current = head;
int i = 0;
while (current.next != null && i < index - 1)
{
current = current.next;
i++;
}
if (current.next != null)
{
current.next = current.next.next;
if (current.next != null)
current.next.prev = current;
}
}
}
public class Program
{
public static void Main()
{
LinkedList ll = new LinkedList();
ll.Add(10);
ll.Add(20);
ll.Add(30);
ll.Delete(1);
}
}Write a C# program to create a skip list.
using System;
using System.Collections.Generic;
public class Node
{
public int data;
public List<Node> forward;
public Node(int data)
{
this.data = data;
this.forward = new List<Node>();
}
}
public class SkipList
{
public Node head;
public int maxLevel;
public SkipList(int maxLevel)
{
this.maxLevel = maxLevel;
head = new Node(int.MinValue);
for (int i = 0; i < maxLevel; i++)
head.forward.Add(null);
}
public void Insert(int data)
{
Node current = head;
List<Node> update = new List<Node>();
for (int i = maxLevel - 1; i >= 0; i--)
{
while (current.forward[i] != null &&
current.forward[i].data < data)
{
current = current.forward[i];
}
update.Add(current);
}
current = new Node(data);
for (int i = 0; i < maxLevel; i++)
{
current.forward[i] = update[i].forward[i];
update[i].forward[i] = current;
}
}
}
public class Program
{
public static void Main()
{
SkipList sl = new SkipList(5);
sl.Insert(10);
sl.Insert(20);
sl.Insert(30);
}
}