Home | Projects | Notes > Data Structures & Algorithms > Singly-Linked Lists

Singly-Linked Lists

Singly-Linked List (C++)

Interface

xxxxxxxxxx
45
1
//==============================================================================
2
// File     : singly_linked_list.h
3
// Brief    : Interface for Singly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : May 02, 2023
6
//==============================================================================
7

8
#ifndef SINGLY_LINKED_LIST_H
9
#define SINGLY_LINKED_LIST_H
10

11
// Class for singly-linked list nodes
12
class Node
13
{
14
public:
15
    int value;
16
    Node *next;
17

18
    Node(int value);                    // Constructor
19
};
20

21
// Class for singly-linked lists
22
class SinglyLinkedList
23
{
24
public:    
25
    // Public interface
26
    SinglyLinkedList(int value);        // Constructor
27
    void append(int value);             // Add a node at the end
28
    void prepend(int value);            // Add a node at the front
29
    bool insert(int index, int value);  // Insert a node into the given index position
30
    void deleteNode(int index);         // Delete a node with the given index position
31
    void deleteLast();                  // Delete the last node
32
    void deleteFirst();                 // Delete the first node
33
    Node* get(int index);               // Get the node value of the given index position
34
    bool set(int index, int value);     // Set the node value of the given index position
35
    void reverse();                     // Reverse the list
36
    void printList();                   // Print the list
37
    ~SinglyLinkedList();                // Destructor
38

39
private:
40
    Node *head;
41
    Node *tail;
42
    int length;
43
};
44

45
#endif

Implementation

xxxxxxxxxx
292
1
//==============================================================================
2
// File     : singly_linked_list.cpp
3
// Brief    : Implementation of Singly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : May 02, 2023
6
//==============================================================================
7

8
#include <iostream>
9
#include <cstdlib>      // EXIT_FAILURE
10
#include "singly_linked_list.h"
11

12
using namespace std;
13

14
//------------------------------------------------------------------------------
15
// Implementation of Node class interface
16
//------------------------------------------------------------------------------
17

18
// Constructor
19
Node::Node(int value)
20
{
21
    this->value = value;
22
    next = nullptr;
23
}
24

25
//------------------------------------------------------------------------------
26
// Implementation of SinglyLinkedList class interface
27
//------------------------------------------------------------------------------
28

29
// Constructor
30
// T = O(1)
31
SinglyLinkedList::SinglyLinkedList(int value)
32
{
33
    Node *newNode = new Node(value);
34
    head = newNode;
35
    tail = newNode;
36
    length = 1;
37
}
38

39
// Add a node at the end
40
// T = O(1)
41
void SinglyLinkedList::append(int value) 
42
{
43
    Node *newNode = new Node(value);
44

45
    // Insert a node into an empty list
46
    if (length == 0)    // (head == nullptr) or (tail == nullptr)
47
    {
48
        head = newNode;
49
        tail = newNode;
50
    }   
51
    // Insert a node into a non-empty list
52
    else
53
    {
54
        tail->next = newNode;
55
        tail = newNode;
56
    }
57

58
    length++;
59
}
60

61
// Add a node at the front
62
// T = O(1)
63
void SinglyLinkedList::prepend(int value)
64
{
65
    Node *newNode = new Node(value);
66

67
    // Insert a node into an empty list
68
    if (length == 0)
69
    {
70
        head = newNode;
71
        tail = newNode;
72
    }
73
    // Insert a node into a non-empty list
74
    else
75
    {
76
        newNode->next = head;
77
        head = newNode;
78
    }
79

80
    length++;
81
}
82

83
// Insert a node into the given index position
84
// T = O(n)
85
bool SinglyLinkedList::insert(int index, int value)
86
{
87
    // Validity check for index
88
    if (index < 0 || index > length)
89
        return false;
90

91
    // Insert a node at front (prepend)
92
    if (index == 0)
93
    {
94
        prepend(value);
95
        return true;
96
    }
97

98
    // Insert a node at the end (append)
99
    if (index == length)
100
    {
101
        append(value);
102
        return true;
103
    }
104

105
    // Insert a node somewhere in the middle
106
    Node *newNode = new Node(value);
107
    Node *temp = get(index - 1);
108
    newNode->next = temp->next;
109
    temp->next = newNode;
110

111
    length++;
112

113
    return true;
114
}
115

116
// Delete a node with the given index position
117
// T = O(n)
118
void SinglyLinkedList::deleteNode(int index)
119
{
120
    // Validity check for index
121
    if (index < 0 || index >= length)
122
        return;
123

124
    // Delete the first node
125
    if (index == 0)
126
        return deleteFirst();   // Available only when return types are the same
127

128
    // Delete the last node
129
    if (index == length - 1)
130
        return deleteLast();
131

132
    // Delete the node from somewhere in the middle
133
    Node *before = get(index - 1);
134
    Node *delNode = before->next;
135
    before->next = delNode->next;
136
    delete delNode;
137

138
    length--;
139
}
140

141
// Delete the last node
142
// T = O(n)
143
void SinglyLinkedList::deleteLast()
144
{
145
    // Do not allow delete operation on an empty list
146
    if (length == 0)
147
    {
148
        cout << "ERROR: Cannot delete from an empty list. Terminating!" << endl;
149
        exit(EXIT_FAILURE);
150
    }
151

152
    Node *delNode = head;
153

154
    // If only 1 node in the list
155
    if (length == 1)
156
    {
157
        head = nullptr;
158
        tail = nullptr;
159
    }
160
    // If 2+ nodes in the list
161
    else
162
    {
163
        Node *before = head;
164

165
        while (delNode->next)
166
        {
167
            before = delNode;
168
            delNode = delNode->next;
169
        }
170

171
        tail = before;
172
        tail->next = nullptr;
173
    }
174

175
    delete delNode;
176
    length--;
177
}
178

179
// Delete the first node
180
// T = O(1)
181
void SinglyLinkedList::deleteFirst()
182
{
183
    // Do not allow delete operation on an empty list
184
    if (length == 0)
185
    {
186
        cout << "ERROR: Cannot delete from an empty list. Terminating!" << endl;
187
        exit(EXIT_FAILURE);
188
    }
189

190
    Node *delNode = head;
191

192
    // If only 1 node in the list
193
    if (length == 1)
194
    {
195
        head = nullptr;
196
        tail = nullptr;
197
    }
198
    // If 2+ nodes in the list
199
    else
200
        head = head->next;
201

202
    delete delNode;
203
    length--;
204
}
205

206
// Get the node value of the given index position
207
// T = O(n)
208
Node* SinglyLinkedList::get(int index)
209
{
210
    // Validity check for index
211
    if (index < 0 || index >= length)
212
        return nullptr;
213

214
    Node *temp = head;
215

216
    // Search for the node
217
    for (int i = 0; i < index; i++)
218
        temp = temp->next;
219

220
    return temp;
221
}
222

223
// Set the node value of the given index position
224
// T = O(n)
225
bool SinglyLinkedList::set(int index, int value)
226
{
227
    // Get the node
228
    Node *temp = get(index);
229

230
    // Set the value
231
    if (temp)
232
    {
233
        temp->value = value;
234
        return true;
235
    }
236

237
    return false;
238
}
239

240
// Reverse the list
241
// T = O(n)
242
void SinglyLinkedList::reverse()
243
{
244
    // Swap head and tail
245
    Node *temp = head;
246
    head = tail;
247
    tail = temp;
248

249
    Node *after = temp->next;
250
    Node *before = nullptr;
251

252
    // Iteratively reverse the direction of next pointer
253
    for (int i = 0; i < length; i++)
254
    {
255
        after = temp->next;
256
        temp->next = before;
257
        before = temp;
258
        temp = after;
259
    }
260
}
261

262
// Print the list
263
// T = O(n)
264
void SinglyLinkedList::printList()
265
{
266
    Node *temp = head;
267

268
    while (temp)
269
    {
270
        cout << temp->value << " ";
271
        temp = temp->next;
272
    }
273

274
    cout << endl;
275
}
276

277
// Destructor
278
// T = O(n)
279
SinglyLinkedList::~SinglyLinkedList()
280
{
281
    // head, tail, length will be destroyed by default, but the nodes will not.
282
    // So, make sure to delete them manually in the destructor.
283

284
    Node *delNode = head;
285

286
    while (head)
287
    {
288
        head = head->next;
289
        delete delNode;
290
        delNode = head;
291
    }
292
}

Test Driver

xxxxxxxxxx
57
1
//==============================================================================
2
// File     : main.cpp
3
// Brief    : Test driver for Singly-Linked List
4
// Author   : Kyungjae Lee
5
// Date     : May 02, 2023
6
//==============================================================================
7

8
#include <iostream>
9
#include "singly_linked_list.h"
10

11
using namespace std;
12

13
int main(int argc, char *argv[])
14
{
15
    // Create a list
16
    SinglyLinkedList *sll = new SinglyLinkedList(2);
17
    
18
    // Prepend
19
    sll->prepend(1);
20

21
    // Append
22
    sll->append(4);
23
    sll->append(5);
24
    sll->append(6);
25

26
    // Insert (insert 3 at index 2)
27
    sll->insert(2, 3);  
28

29
    // Print the list
30
    sll->printList();       // 1 2 3 4 5 6
31

32
    // Delete first
33
    sll->deleteFirst();
34

35
    // Delete last
36
    sll->deleteLast();
37

38
    // Delete from the middle (index 1)
39
    sll->deleteNode(1);
40

41
    // Print the list
42
    sll->printList();       // 2 4 5
43

44
    // Set (value of the node at index 1 to 10)
45
    sll->set(1, 10);
46

47
    // Get (value of the node at index 1 to 10)
48
    cout << sll->get(1)->value << endl; // 10
49

50
    // Reverse the list
51
    sll->reverse();
52

53
    // Print the list
54
    sll->printList();       // 5 10 2
55

56
    return 0;
57
}

xxxxxxxxxx
4
1
1 2 3 4 5 6 
2
2 4 5 
3
10
4
5 10 2