Data structures

Jump to Section:

Linked list

A linked list represents a set of linked nodes, each of which stores the data itself and a link to the next node. In real life, a linked list can be thought of as a train, each car of which can contain cargo or passengers and can also be linked to another car.

 

365

Thus, if in an array the position of elements is determined by indices, then in a linked list it is determined by pointers to the next and/or) previous element.

Linked lists can vary. There are singly linked lists, in which each node stores a pointer only to the next node. There are doubly linked lists, in which each element stores a reference to both the next element and the previous one. There are also circular, closed lists. In this case, we will consider creating a singly linked list.

Before creating a list, we need to define a node class that will represent a single object in the list:

1
2
3
4
5
6
7
8
9
public class Node<T>
{
public Node(T data)
{
Data = data;
}
public T Data { get; set; }
public Node<T>? Next { get; set; }
}

The Node class is generic, so it can store any type of data. The property is used to store data Data. The property is defined to reference the next node Next.

Next, we define the list class itself:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
using System.Collections;
using System.Collections.Generic;public class LinkedList<T> : IEnumerable<T> // singly linked list
{
Node<T>? head; // head/first element
Node<T>? tail; // last/tail element
int count; // number of elements in the list

// adding an element
public void Add(T data)
{
Node<T> node = new Node<T>(data);

if (head == null)
head = node;
else
tail!.Next = node;
tail = node;

count++;
}
// removing an element
public bool Remove(T data)
{
Node<T>? current = head;
Node<T>? previous = null;

while (current != null && current.Data != null)
{
if (current.Data.Equals(data))
{
// If the node is in the middle or at the end
if (previous != null)
{
// remove the current node, now previous points to current.Next instead of current
previous.Next = current.Next;

// If current.Next is not set, then the node is the last one,
// change the tail variable
if (current.Next == null)
tail = previous;
}
else
{
// if the first element is being removed
// reset the head value
head = head?.Next;

// if the list is empty after removal, reset the tail
if (head == null)
tail = null;
}
count–;
return true;
}

previous = current;
current = current.Next;
}
return false;
}

public int Count { get { return count; } }
public bool IsEmpty { get { return count == 0; } }
// clearing the list
public void Clear()
{
head = null;
tail = null;
count = 0;
}
// whether the list contains the element
public bool Contains(T data)
{
Node<T>? current = head;
while (current != null && current.Data != null)
{
if (current.Data.Equals(data)) return true;
current = current.Next;
}
return false;
}
// adding to the beginning
public void AppendFirst(T data)
{
Node<T> node = new Node<T>(data);
node.Next = head;
head = node;
if (count == 0)
tail = head;
count++;
}

IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
Node<T>? current = head;
while (current != null)
{
yield return current.Data;
current = current.Next;
}
}

// implementation of the IEnumerable interface
IEnumerator IEnumerable.GetEnumerator()
{
return ((IEnumerable<T>)this).GetEnumerator();
}
}

Let’s go over the main points. List implementations may vary depending on the specific tasks, but all implementations share two key methods: adding and deleting.

But before performing various operations on the data, three variables are defined in the list class:

1
2
3
Node<T>? head; // head/first element
Node<T>? tail; // last/tail element
int count; // number of elements in the list

Adding method:

1
2
3
4
5
6
7
8
9
10
11
12
public void Add(T data)
{
Node<T> node = new Node<T>(data);if (head == null)
head = node;
else
tail!.Next = node;
tail = node;

count++;
}

If the head variable isn’t set (meaning the list is empty), then we set head and tail. After adding the first element, they will point to the same object.

If the list contains at least one element, we set the tail. Next property—it now stores a reference to the new node. We then reset tail—it now refers to the new node.

The complexity of this method is O(1). Graphically, it looks like this:

 

365

It’s important to note the presence of the tail variable, which points to the last element. Some implementations don’t use this variable and instead add it differently:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void AddWithoutTail(T data)
{
Node<T> node = new Node<T>(data);if (head == null)
{
head = node;
}
else
{
Node<T> current = head;
// find the last element
while (current.Next != null)
{
current = current.Next;
}
// set the last element
current.Next = node;
}
count++;
}

This method is quite effective and is often used, but the need to iterate through elements to find the last one increases the search time and the complexity of the algorithm. It is O(n) .

A special method is adding to the beginning of a list, where we simply reset the reference to the head element:

1
2
3
4
5
6
7
8
9
public void AppendFirst(T data)
{
Node<T> node = new Node<T>(data);
node.Next = head;
head = node;
if (count == 0)
tail = head;
count++;
}

Deleting an element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public bool Remove(T data)
{
Node<T>? current = head;
Node<T>? previous = null;while (current != null && current.Data != null)
{
if (current.Data.Equals(data))
{
// If the node is in the middle or at the end
if (previous != null)
{
// remove the current node, now previous points to current.Next instead of current
previous.Next = current.Next;

// If current.Next is not set, then the node is the last one,
// change the tail variable
if (current.Next == null)
tail = previous;
}
else
{
// if the first element is being removed
// reset the head value
head = head?.Next;

// if the list is empty after removal, reset the tail
if (head == null)
tail = null;
}
count–;
return true;
}
previous = current;
current = current.Next;
}
return false;
}

The algorithm for deleting an element is the following sequence of steps:

  1. Finding an element in a list by iterating over all elements
  2. Sets the Next property of the previous node (relative to the one being deleted) to the next node relative to the one being deleted.

The variable is used to track the previous node previous. If an element is found and the variable previous is null, deletion starts over, and in this case, the variable head (the head element) is reset.

If the previous is not null, then the steps of the algorithm described above are implemented.

The complexity of this algorithm is O(n). Graphically, deletion can be represented as follows:

 

365

To check if an element exists, the Contains method is used:

1
2
3
4
5
6
7
8
9
10
11
public bool Contains(T data)
{
Node<T>? current = head;
while (current != null && current.Data != null)
{
if (current.Data.Equals(data))
return true;
current = current.Next;
}
return false;
}

Here again, a simple enumeration is performed. The algorithmic complexity of the method is O(n) .

And for the list to be iterated over in an external program using a for-each loop, the list class implements the IEnumerable interface :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// implementation of the IEnumerable interface
IEnumerator IEnumerable.GetEnumerator()
{
return ((IEnumerable<T>)this).GetEnumerator();
}IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
Node<T>? current = head;
while (current != null)
{
yield return current.Data;
current = current.Next;
}
}

Implementing this interface isn’t an integral part of singly linked lists, but it does provide an efficient method for iterating over a collection in a foreach loop. Otherwise, we’d have to implement our own list-iterating constructs.

Using LinkedList:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
LinkedList<string> linkedList = new LinkedList<string>
{
// adding elements
“Tom”,
“Alice”,
“Bob”,
“Sam”
};// printing elements
foreach (var item in linkedList)
{
Console.WriteLine(item);
}

// removing an element
linkedList.Remove(“Alice”);
Console.WriteLine(“\nAfter removing Alice:”);
foreach (var item in linkedList) Console.WriteLine(item);

// checking if an element exists
bool isPresent = linkedList.Contains(“Sam”);
Console.WriteLine(isPresent ? “Sam is present” : “Sam is absent”);

// adding an element to the beginning
linkedList.AddFirst(“Bill”);
Console.WriteLine(“\nAfter adding Bill:”);
foreach (var item in linkedList) Console.WriteLine(item);

Console output:

Tom
Alice
Bob
Sam

After deleting Alice
Tom
Bob
Sam
Sam is present

After adding Billa
Bill
Tom
Bob
Sam

Explore More IT Terms

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Share this term: Facebook X LinkedIn WhatsApp Email
CONTINUE LEARNING Next: Doubly linked lists →

RELATED ARTICLES

Circular singly linked list

    Deque

      Queue

        Stack

          Array-based stack

            Algorithms and Data Structures in C#

              Leave a Reply

              Your email address will not be published. Required fields are marked *

              Powered by
              ►
              Necessary cookies enable essential site features like secure log-ins and consent preference adjustments. They do not store personal data.
              None
              ►
              Functional cookies support features like content sharing on social media, collecting feedback, and enabling third-party tools.
              None
              ►
              Analytical cookies track visitor interactions, providing insights on metrics like visitor count, bounce rate, and traffic sources.
              None
              ►
              Advertisement cookies deliver personalized ads based on your previous visits and analyze the effectiveness of ad campaigns.
              None
              Powered by