Doubly linked lists

⏱️ Estimated Reading Time: ~5 min read
0
(0)

Doubly linked lists also represent a sequence of linked nodes, but each node now stores references to the next and previous nodes.

 

365

The doubly linked nature of a list must be taken into account when adding or removing an element, since in addition to a reference to the next element, a reference to the previous element must also be established. However, at the same time, we can traverse the list from the first to the last element, as well as from the last to the first element. Otherwise, a doubly linked list is no different from a singly linked list.

To create a doubly linked list, you first need to define a node class that will represent a list element:

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

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
using System.Collections.Generic;
using System.Collections;namespace SimpleAlgorithmsApp
{
public class DoublyLinkedList<T> : IEnumerable<T> // doubly linked list
{
DoublyNode<T> head; // head/first element
DoublyNode<T> tail; // last/tail element
int count; // number of elements in the list

// adding an element to the end
public void Add(T data)
{
DoublyNode<T> node = new DoublyNode<T>(data);

if (head == null)
head = node;
else
{
tail.Next = node;
node.Previous = tail;
}
tail = node;
count++;
}

// adding an element to the beginning
public void AddFirst(T data)
{
DoublyNode<T> node = new DoublyNode<T>(data);
DoublyNode<T> temp = head;
node.Next = temp;
head = node;
if (count == 0)
tail = head;
else
temp.Previous = node;
count++;
}

// removing an element
public bool Remove(T data)
{
DoublyNode<T> current = head;

// search for the node to remove
while (current != null)
{
if (current.Data.Equals(data))
{
break;
}
current = current. Next;
}

if (current != null)
{
// if the node is not the last one
if (current.Next != null)
{
current.Next.Previous = current.Previous;
}
else
{
// if it is the last one, reset the tail
tail = current.Previous;
}

// if the node is not the first one
if (current.Previous != null)
{
current.Previous.Next = current.Next;
}
else
{
// if it is the first one, reset the head
head = current. Next;
}
count–;
return true;
}
return false;
}

public int Count { get { return count; } }
public bool IsEmpty { get { return count == 0; } }

public void Clear()
{
head = null;
tail = null;
count = 0;
}

public bool Contains(T data)
{
DoublyNode<T> current = head;
while (current != null)
{
if (current.Data.Equals(data))
return true;
current = current. Next;
}
return false;
}

// Non-generic enumerator (Fixed to call the generic implementation to avoid stack overflow)
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}

// Forward enumerator
public IEnumerator<T> GetEnumerator()
{
DoublyNode<T> current = head;
while (current != null)
{
yield return current. Data;
current = current. Next;
}
}

// Backward enumerator
public IEnumerable<T> BackEnumerator()
{
DoublyNode<T> current = tail;
while (current != null)
{
yield return current. Data;
current = current.Previous;
}
}
}
}

Basically, this doubly linked list implements the same actions as a singly linked list; the difference is the need to set the Previous property for the list nodes.

In the add method Add()if the list already contains elements, the property of the node being added Previouspoints to the node that was previously stored in the tail variable:

1
2
3
4
5
6
7
8
if (head == null)
head = node;

 

365

Similarly, in the AddFirstprepending method, the head element’s Previous property begins pointing to the new element, and the new element thus becomes the first element in the list.

 

365

When deleting, you first need to find the element to be deleted. Then, in general, you need to reset two links:

1
2
current.Next.Previous = current.Previous;

If the first and last elements are removed, the head and tail variables must be reset accordingly.

 

365

And also, unlike the single-linked implementation, a method BackEnumerator()for iterating over elements from the end has been added here.

Using the list:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

DoublyLinkedList<string> linkedList = new DoublyLinkedList<string>();

// adding elements
linkedList.Add(“Bob”);
linkedList.Add(“Bill”);
linkedList.Add(“Tom”);
linkedList.AddFirst(“Kate”);

// displaying elements in forward order
Console.WriteLine(“Forward iteration:”);
foreach (var item in linkedList)
{
Console.WriteLine(item);
}

// removing an element
linkedList.Remove(“Bill”);

Console.WriteLine(“\nBackward iteration after removing Bill:”);
// iterating from the last element
foreach (var t in linkedList.BackEnumerator())
{
Console.WriteLine(t);
}

Forward iteration:
Kate
Bob
Bill
Tom

Backward iteration after removing Bill:
Tom
Bob
Kate

How useful was this post?

Click on a star to rate it!

Average rating 0 / 5. Vote count: 0

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

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: Algorithms and Data Structures in C# →

RELATED ARTICLES

Complexity of algorithms-Tutorial

    Algorithm complexity: deep parsing O(log n)

    Algorithm complexity: deep parsing O(log n)

      Algorithm Analysis

        Homogeneous vs. non-homogeneous structures

        Homogeneous vs. non-homogeneous structures

          Static vs. dynamic data structures

          Static vs. dynamic data structures

            Linear vs. non-linear data structures

            Linear vs. non-linear data structures

              Leave a Reply

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

              Powered by