Singly and doubly linked lists (also known simply as Linked Lists) hold collection of elements, which preserve their order. Unlike arrays that occupy contiguous memory spaces, linked lists are pointer-based, allowing for flexible, non-contiguous memory allocation (elements of the collection don't need to be allocated one after the other in the same memory region). This structure facilitates additions and deletions at any point in the list, particularly quick at the ends, making linked lists well-suited for implementing data structures like stacks and queues. They are linked sequences of elements.
Additional Information
Pointers are memory addresses, and you can visualize them like signs that tell you where to find something in memory. In C#, while you can use pointers like they are used in other languages, such as C or C++, we actually use something similar, called references. When I say linked lists are "pointer-based," I mean they use these references to link together all the items in the list. Each item in the list has a reference that points to the next item, creating a chain. This is how linked lists keep track of all their elements in order, and this is also why their elements don't need to be allocated in memory at addresses one after the other, because each node can point to another node located at any memory address.
The difference between single and double linked lists is that in the case of single linked lists, each node points only to the next node in the chain, making it a "one-way" direction flow. In a doubly linked list, each node holds references (points) to both the next and the previous elements in the list, allowing for bi-directional navigation.
The main difference between linked lists and data structures like arrays and lists is that since they use pointers to "point" to the next element in sequence, they don't offer indexed access. In non-academic language, this means that you can't directly access "the third element", like you could in an array or a list. Instead, you would have to start either at the start or the end of the linked list and "navigate" from node pointing to the next node, pointing to the next node, until you find the node you are actually looking for. This means that adding and removing elements at the ends of a linked list is efficient, but that efficiency goes down the more your manipulated element is deeper in the structure.
Because of this, linked lists are not as commonly used as lists, which offer faster operations for most needs and are more memory-efficient. Lists usually provide the same capabilities with less overhead and more predictability in performance. One example where a linked list might be preferred over a normal array or list would be when dealing with a very large data structure, and you would want to add or remove elements in the middle of it - all subsequent elements must be moved, shifted, and that is a costly operation. When using a linked list, it would only mean "breaking the chain" to insert or remove the elements at that location, and updating the adjacent references that point to them.
Searching in a linked list is a slow operation because we have to traverse through all of its elements.
Example usage:
|
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
|
using
System;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// create a new linked list
LinkedList<string> linkedList = new LinkedList<string>();
// use AddLast method to add elements at the end
linkedList.AddLast("cat");
linkedList.AddLast("dog");
linkedList.AddLast("man");
// use AddFirst method to add element at the start
linkedList.AddFirst("one");
// insert a node before the second node (after the first node)
LinkedListNode<string> node = linkedList.Find("one");
linkedList.AddAfter(node, "inserted");
// loop through the linked list
foreach (var value in linkedList);
Console.WriteLine(value);
Console.ReadLine();
}
}
}
|
The main methods of a Linked List are the following:
AddFirst(), AddLast(), AddBefore(), AddAfter() - appends or prepends elements to the linked list's internal data structure, respectively, adds before or after a certain element. Example:
|
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
|
using
System;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// create a new linked list
LinkedList<string> linkedList = new LinkedList<string>();
// use AddLast method to add elements at the end
linkedList.AddLast("cat");
linkedList.AddLast("dog");
linkedList.AddLast("man");
// use AddFirst method to add element at the start
linkedList.AddFirst("first");
// add a new element after a certain other element
LinkedListNode<string> node = linkedList.FindLast("dog");
linkedList.AddAfter(node, "cow");
// add a new element before a certain other element
linkedList.AddBefore(node, "bird");
// loop through the linked list
foreach (var value in linkedList);
Console.WriteLine(value);
Console.ReadLine();
}
}
}
|
Find(), FindLast() - searches for an element in its internal collection of elements. It returns a reference to an instance of the LinkedListNode class, which contains pointers to the other elements (the results of the search). Example:
|
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
|
using
System;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// create a new linked list
LinkedList<string> linkedList = new LinkedList<string>();
// first, add three elements to the linked list
linkedList.AddLast("one");
linkedList.AddLast("two");
linkedList.AddLast("three");
// insert a node containing the results of a search, before the second node (after the first node)
LinkedListNode<string> node = linkedList.Find("one");
linkedList.AddAfter(node, "inserted");
// loop through the linked list
foreach (var value in linkedList);
Console.WriteLine(value);
Console.ReadLine();
}
}
}
|
Remove(), RemoveFirst(), RemoveLast() - exactly what their name suggests: the first removes a certain node, the others remove first or last elements. Example:
|
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
|
using
System;
namespace
HelloWorld
{
class
Program
{
static void Main(string[] args)
{
// create a new linked list
LinkedList<string> linkedList = new LinkedList<string>();
// first, add three elements to the linked list
linkedList.AddLast("one");
linkedList.AddLast("two");
linkedList.AddLast("three");
// remove first and last elements, as well as some random node
linkedList.RemoveFirst();
linkedList.RemoveLast();
LinkedListNode<string> node = linkedList.Find("two");
linkedList.Remove(node);
// loop through the linked list
foreach (var value in linkedList);
Console.WriteLine(value);
Console.ReadLine();
}
}
}
|
As the previous data structures we have learned so far, linked lists also contain some common methods like Clear(), Contains(), CopyTo(), etc.
The most important properties of a linked list are:
Count - returns the number of elements in the list
First - gets the first node of the list
Last - gets the last node of the list.