Alexandar May's Blog
0%

Singly Linked List

Posted on Edited on In
Symbols count in article: 5.3k Reading time ≈ 5 mins.

Singly Linked List: Concepts and Operations

  1. Overview of Singly Linked List
  2. Advantages of Linked List
  3. Types of Linked List
  4. How to Create a Linked List
  5. Various Operations on Linked List

Overview of Singly Linked List

What is a Linked List?
In C#, a linked list is a linear data structure that stores elements in non - contiguous memory locations.
Each node consists of two parts:

  1. Data: Each node of a linked list can store a piece of data.
  2. Address: Each node of a linked list contains the address of the next node, referred to as “Next”.

pic
The first node of a linked list is referenced by a pointer called “Head”.

Advantages of Linked List

  1. They are dynamic in nature and allocate memory as needed.
  2. Insertion and deletion operations are easy to implement.
  3. Other data structures such as stacks and queues can also be easily implemented using linked lists.
  4. They have fast access times and can be expanded in constant time without memory overhead.
  5. Since there is no need to define an initial size for a linked list, memory utilization is efficient.
  6. Backtracking is possible in doubly - linked lists.

Node Class

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

Types of Linked List

  • Singly linked lists
  • Doubly linked lists
  • Circular linked lists
  • Circular doubly linked lists

How to Create a Linked List

Combined with the above node class, you can gradually build a linked list by instantiating nodes and setting their Next pointers. For example:

1
2
3
Node<int> node1 = new Node<int>(1);
Node<int> node2 = new Node<int>(2);
node1.Next = node2;

// Here, node1 serves as the head node to build a simple linked list

Various Operations on Linked List

Linked List Class Definition

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
130
131
132
133
134
135
136
137
138
139
140
141
142
public class LinkedList<T>
{
    // The head node of the linked list
    private Node<T> head;
    // The length of the linked list
    private int length;

    public LinkedList()
    {
        head = null;
        length = 0;
    }

    public int Length => length;
    public bool IsEmpty() => (length == 0);

    // Add a new node at the beginning of the linked list
    public void AddFirst(T data)
    {
        Node<T> newNode = new Node<T>(data);
        newNode.Next = head;
        // Update the new node as the head of the linked list
        head = newNode;
        length++;
    }
    // Add a new node at the end of the linked list
    public void AddTail(T data)
    {
        Node<T> newNode = new Node<T>(data);
        if (head == null)
        {
            head = newNode;
            return;
        }
        Node<T> current = head;
        while (current.Next != null)
        {
            current = current.Next;
        }
        current.Next = newNode;
        length++;
    }

    public void DeleteElemets(T Data)
    {
        Node<T> dummyHead = new Node<T>(default(T));
        dummyHead.Next = head;
        Node<T> temp = dummyHead;
        while (temp.Next != null)
        {
            if (temp.Next.Data.Equals(Data))
            {
                temp.Next = temp.Next.Next;
                length--;
            }
            else
            {
                temp = temp.Next;
            }
        }
        // return dummyHead.Next;
    }
    public void Delete(T Data)
    {
        if (head == null) return;
        if (head.Data.Equals(Data))
        {
            head = head.Next;
            length--;
            return;
        }
        Node<T> current = head;
        while (current != null && current.Next != null)
        {
            if (current.Next.Data.Equals(Data))
            {
                current.Next = current.Next.Next;
                length--;
                return;
            }
            current = current.Next;
        }
    }
    public void DeleteAtHead()
    {
        if (head == null) return;
        head = head.Next;
        length--;
    }
    public void Find(T Data)
    {
        Node<T> current = head;
        while (current != null)
        {
            if (current.Data.Equals(Data))
            {
                Console.WriteLine("Found the data: " + Data);
                return;
            }
            current = current.Next;
        }
        Console.WriteLine("Not Found the data: " + Data);
    }

    public void InsertAt(int index, T data)
    {
        if (index < 0)
        {
            throw new ArgumentOutOfRangeException("Index", index, "Index must be non - negative");
        }
        Node<T> newNode = new Node<T>(data);
        if (index == 0)
        {
            AddFirst(data);
            return;
        }
        Node<T> current = head;
        for (int i = 0; i < index - 1; i++)
        {
            if (current == null || current.Next == null)
            {
                throw new ArgumentOutOfRangeException("Index", index, "Index is out of range");
            }
            current = current.Next;
        }
        newNode.Next = current.Next;
        current.Next = newNode;
        length++;
    }

    public void Print()
    {
        Node<T> current = head;
        while (current != null)
        {
            Console.Write(current.Data + "->");
            current = current.Next;
        }
        Console.Write("null");
        Console.WriteLine();
    }
}

Additional Exercises:

How to Reverse a Linked List?

The time complexity is , and the space complexity is .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void ReverseList()
{
    if (head.Next == null || head.Next.Next == null)
    {
        return;
    }
    Node<T> pre = null;
    Node<T> current = head;
    Node<T> temp = null;
    while (current != null)
    {
        // Store the key node to prevent data loss
        temp = current.Next;
        current.Next = pre;
        pre = current;
        current = temp;
    }
    head = pre;
}

How to Find the k - th Node from the End of the Linked List

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
public Node<T> FindKthToLast(int k)
{
    if (head == null || k <= 0)
    {
        return null;
    }
    Node<T> fast = head;
    Node<T> slow = head;
    // Let the fast pointer move k steps first, and the remaining is N - K steps, which is the K - th step from the end
    for (int i = 0; i < k; i++)
    {
        if (fast == null)
        {
            return null;
        }
        fast = fast.Next;
    }
    // Move the fast and slow pointers together, and the slow pointer moves N - K steps
    while (fast != null)
    {
        fast = fast.Next;
        slow = slow.Next;
    }
    return slow;
}