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

Singly-Linked Lists

Introduction

A singly linked list is a linear data structure made up of nodes, where each node contains a data value and a pointer to the next node in the sequence. The list is traversed in one direction — from the front to the back — by following these next pointers. It supports dynamic memory usage and is ideal for frequent insertions or deletions at known positions.

singly-linked-list

Pros:

Dynamic Size: Easily grows or shrinks without reallocating or copying (unlike arrays).
Efficient Insertion/Deletion: O(1) time to insert or delete at the head (or with a known pointer).
Low Memory Overhead per Element: Requires only one pointer (next) per node.
No Wasted Space: No need to preallocate or resize like arrays.

Cons:

No Random Access: Accessing the n-th element takes O(n) time; cannot do list[i] like arrays.
Sequential Traversal Only: Cannot traverse backward; no prev pointer.
More Memory per Element Than Arrays: Each node stores a pointer along with data.
Cache Unfriendly: Nodes are not contiguous in memory, leading to poor cache performance compared to arrays or vectors.

Compared to Arrays:

Better: Insert/delete at front/back (if back pointer is maintained).
Worse: Random access, cache locality, memory overhead.

Implementation (C++)

Header (`slist.hpp`)


41
1
#ifndef SLIST_HPP
2
#define SLIST_HPP
3

4
#include <iostream>
5

6
class node
7
{
8
public:
9
    node(int val) : data(val), p_next(nullptr) {}
10

11
    int data;
12
    node *p_next;
13
};
14

15
class slist
16
{
17
public:
18
    slist() : p_front(nullptr), cnt(0) {}
19
    ~slist() { clear(); }
20
    void push_front(const int val);
21
    void push_back(const int val);
22
    void insert_at(const int idx, const int val);
23
    void pop_front();
24
    void pop_back();
25
    void erase_at(const int idx);
26
    void erase_val(const int val);
27
    int get_at(const int idx) const;
28
    int find(const int val) const;
29
    int front() const;
30
    int back() const;
31
    int size() const;
32
    bool empty() const;
33
    void clear();
34
    void print() const;
35
    
36
private:
37
    node *p_front;
38
    int cnt;
39
};
40

41
#endif

Source (`slist.cpp`)


252
1
#include "slist.hpp"
2
#include <stdexcept>
3

4
void slist::push_front(const int val)
5
{
6
    node *p_new = new node(val);
7
    p_new->p_next = p_front;
8
    p_front = p_new;
9
    ++cnt;
10
}
11

12
void slist::push_back(const int val)
13
{
14
    node *p_new = new node(val);
15

16
    if (!p_front)
17
    {
18
        p_front = p_new;
19
    }
20
    else
21
    {
22
        node *p_temp = p_front;
23

24
        while (p_temp->p_next)
25
        {
26
            p_temp = p_temp->p_next;
27
        }
28

29
        p_temp->p_next = p_new;
30
    }
31

32
    ++cnt;
33
}
34

35
void slist::insert_at(const int idx, const int val)
36
{
37
    if (idx < 0 || idx > cnt)
38
    {
39
        return;
40
    }
41

42
    if (idx == 0)
43
    {
44
        return push_front(val);
45
    }
46

47
    node *p_new = new node(val);
48
    node *p_temp = p_front;
49

50
    for (int i = 0; i < idx - 1; ++i)
51
    {
52
        p_temp = p_temp->p_next;
53
    }
54

55
    p_new->p_next = p_temp->p_next;
56
    p_temp->p_next = p_new;
57

58
    ++cnt;
59
}
60

61
void slist::pop_front()
62
{
63
    if (!p_front)
64
    {
65
        return;
66
    }
67

68
    node *p_temp = p_front;
69
    p_front = p_front->p_next;
70
    delete p_temp;
71
    --cnt;
72
}
73

74
void slist::pop_back()
75
{
76
    if (!p_front)
77
    {
78
        return;
79
    }   
80

81
    if (!p_front->p_next)
82
    {
83
        delete p_front;
84
        p_front = nullptr;
85
    }
86
    else
87
    {
88
        node *p_temp = p_front;
89

90
        while (p_temp->p_next->p_next)
91
        {
92
            p_temp = p_temp->p_next;
93
        }
94

95
        delete p_temp->p_next;
96
        p_temp->p_next = nullptr;
97
    }
98

99
    --cnt;
100
}
101

102
void slist::erase_at(const int idx)
103
{
104
    if (idx < 0 || idx > cnt)
105
    {
106
        return;
107
    }
108

109
    if (idx == 0)
110
    {
111
        return pop_front();
112
    }
113

114
    node *p_temp = p_front;
115

116
    for (int i = 0; i < idx - 1; ++i)
117
    {
118
        p_temp = p_temp->p_next;
119
    }
120

121
    node *p_del = p_temp->p_next;
122
    p_temp->p_next = p_temp->p_next->p_next;
123
    delete p_del;
124
    --cnt;
125
}
126

127
void slist::erase_val(const int val)
128
{
129
    if (!p_front)
130
    {
131
        return;
132
    }
133

134
    if (val == p_front->data)
135
    {
136
        pop_front();
137
    }
138

139
    node *p_temp = p_front;
140

141
    while (p_temp->p_next && val != p_temp->p_next->data)
142
    {
143
        p_temp = p_temp->p_next;
144
    }
145

146
    if (p_temp->p_next)
147
    {
148
        node *p_del = p_temp->p_next;
149
        p_temp->p_next = p_temp->p_next->p_next;
150
        delete p_del;
151
    }
152

153
    --cnt;
154
}
155

156
int slist::get_at(const int idx) const
157
{
158
    if (idx < 0 || idx >= cnt)
159
    {
160
        throw std::out_of_range("Index out of range");
161
    }
162

163
    node *p_temp = p_front;
164

165
    for (int i = 0; i < idx; ++i)
166
    {
167
        p_temp = p_temp->p_next;
168
    }
169

170
    return p_temp->data;
171
}
172

173
int slist::find(const int val) const
174
{
175
    node *p_temp = p_front;
176
    int idx = 0;
177

178
    while (p_temp)
179
    {
180
        if (val == p_temp->data)
181
        {
182
            return idx;
183
        }
184

185
        p_temp = p_temp->p_next;
186
        idx++;
187
    }
188

189
    return -1;
190
}
191

192
int slist::front() const
193
{
194
    if (!p_front)
195
    {
196
        throw std::runtime_error("List is empty");
197
    }
198

199
    return p_front->data;
200
}
201

202
int slist::back() const
203
{
204
    if (!p_front)
205
    {
206
        throw std::runtime_error("List is empty");
207
    }
208

209
    node *p_temp = p_front;
210

211
    while (p_temp->p_next)
212
    {
213
        p_temp = p_temp->p_next;
214
    }
215

216
    return p_temp->data;
217
}
218

219
int slist::size() const
220
{
221
    return cnt;
222
}
223

224
bool slist::empty() const
225
{
226
    return 0 == cnt;
227
}
228

229
void slist::clear()
230
{
231
    while (p_front)
232
    {
233
        node *p_temp = p_front;
234
        p_front = p_front->p_next;
235
        delete p_temp;
236
    }
237

238
    cnt = 0;
239
}
240

241
void slist::print() const
242
{
243
    node *p_temp = p_front;
244

245
    while (p_temp)
246
    {
247
        std::cout << p_temp->data << " -> ";
248
        p_temp = p_temp->p_next;
249
    }
250

251
    std::cout << "null" << std::endl;
252
}

Test Driver


40
1
#include <iostream>
2
#include "slist.hpp"
3

4
int main(int argc, char *argv[])
5
{
6
    slist sl;
7

8
    sl.push_front(1);
9
    sl.push_back(2);
10
    sl.push_back(3);
11
    sl.push_back(4);
12
    sl.push_back(5);
13
    sl.push_back(6);
14
    sl.print();         // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
15

16
    sl.pop_front();
17
    sl.print();         // 2 -> 3 -> 4 -> 5 -> 6 -> null
18
    sl.pop_back();
19
    sl.print();         // 2 -> 3 -> 4 -> 5 -> null
20

21
    sl.insert_at(0, 1); 
22
    sl.print();         // 1 -> 2 -> 3 -> 4 -> 5 -> null
23
    sl.erase_at(1);
24
    sl.print();         // 1 -> 3 -> 4 -> 5 -> null
25
    sl.erase_val(3);
26
    sl.print();         // 1 -> 4 -> 5 -> null
27

28
    std::cout << sl.find(4) << std::endl;   // 1
29
    std::cout << sl.empty() << std::endl;   // 0
30
    std::cout << sl.size() << std::endl;    // 3
31

32
    std::cout << sl.front() << std::endl;   // 1
33
    std::cout << sl.back() << std::endl;    // 5
34
    std::cout << sl.get_at(1) << std::endl; // 4
35

36
    sl.clear();
37
    sl.print();         // null
38

39
    return 0;
40
}


13
1
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
2
2 -> 3 -> 4 -> 5 -> 6 -> null
3
2 -> 3 -> 4 -> 5 -> null
4
1 -> 2 -> 3 -> 4 -> 5 -> null
5
1 -> 3 -> 4 -> 5 -> null
6
1 -> 4 -> 5 -> null
7
1
8
0
9
3
10
1
11
5
12
4
13
null