Web
Analytics Made Easy - StatCounter

Singly Linked Lists (With Code in C, C++, Java, and Python)

Introduction

Singly linked lists are a type of a linked list where each node points to the next node in the sequence. It does not have any pointer that points to the previous node. That means we can traverse the list only in forward direction. Figure 1 shows an example of a singly linked list with 4 nodes.

Fig 1: An example of a singly linked list

The first item in the list is pointed by a pointer called head. Sometimes we use another pointer called tail that points to the last item in the list. I am using only head in this tutorial to make it simple.

Operations on a singly linked list

Insert item at the head

Inserting an item at the head of the list requires 3 steps.

  1. Create a new node. Insert the item in the data field of the node.
  2. Set the new node’s next pointer to the node current head is pointing to.
  3. Make the head pointer point to the newly added node.

Fig 2: Insertion at the head of the list

Insert an item at the end

To insert an item at the end of the list, use following steps.

  1. Seek through the list until the final node is reached.
  2. Create a new node using the item to be inserted.
  3. Set the last node’s next pointer to the newly created node.
  4. Set the next pointer of the new node to null.

Fig 3: Insertion at the end of the list (Steps 1 and 2 are merged together in step 1)

Insert item after another item

To insert an item anywhere between the first and the last node, use the following steps.

  1. Seek through the list until the desired node N (after which you want to insert the new node) is found.
  2. Create a new node using the item to be inserted.
  3. Set the new node’s next pointer to the node N.
  4. Set N’s next pointer to the newly created node.

Fig 4: Insertion at the middle (Steps 1, 2 and 3, 4 are merged together)

Searching an item in the list

Searching for an item in the list requires the following step.

  1. Start with the head.
  2. If the data matches, your search is complete.
  3. If the data does not match, go to the next node and repeat step 2.
  4. If the next of the item is null, we reach the end of the list and data is not found in the list.

Delete item at the head

For all the delete operations, please keep in mind that, the object needs to be deleted from the heap memory. Languages like Java, Python have Garbage Collector that takes care of this but in C/C++ you need to delete the objects yourself

Use the following steps to delete the item at the head of the linked list.

  1. Set the next pointer of the first node to null.
  2. Move the current head of the list to the second node.
  3. Delete the first node.

Fig 5: Deletion at the head of the list

Delete item at the end

Use the following steps to delete the item at the end of the list.

  1. Seek through the list until you get to the last node (You might need to keep track of the previous node as well).
  2. Set the previous node’s next to null.
  3. Delete the last node.

Fig 6: Deletion at the end of the list

Delete item anywhere in the list

  1. Search the list until you find the item you are looking for (You might need to keep track of the previous node as well). Let’s call this node N.
  2. Set N’s previous node’s next to the N’s next node’s next.
  3. Delete N.

Fig 7: Deletion of node anywhere in the list

Complexities

The complexities of the operations discussed above are summarized in the table below.

OperationComplexity
Insert at the headO(1)
Insert at the endO(n)
Insert at the middleO(n)
Delete at the headO(1)
Delete at the endO(n)
Delete at the middleO(n)
Search the listO(n)

The complexities given above are for the linked list that has only head pointer. If we have tail pointer then inserting at the end takes only a constant time.

Implementation in C, C++, Java, and Python

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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
// C implementation of singly linked list
#include <stdio.h>
#include <stdlib.h>



// data structure for Node
// data -> the actual value
// next -> address of the next node
struct Node {
int data;
struct Node *next;
};

typedef struct Node *NodePtr;

// global variable head. It points to the
// first node of the list
NodePtr head = NULL;

// check if the list is empty
int isEmpty() {
return head == NULL;
}

// Insert 'value' at the front of the list
void insertAtFront(int value) {
NodePtr node = malloc(sizeof(NodePtr));
node->data = value;
node->next = NULL;

if (isEmpty()) {
head = node;
} else {
node->next = head;
head = node;
}

}

// insert value at the back of the linked list
void insertAtBack(int value) {
NodePtr node = malloc(sizeof(NodePtr));
node->data = value;
node->next = NULL;

if (isEmpty()) {
head = node;
} else {
// find the last node
NodePtr currPtr = head;
while (currPtr->next != NULL) {
currPtr = currPtr->next;
}

// insert it
currPtr->next = node;
}
}

// inserts value after key
NodePtr insertAfter(int key, int value) {
NodePtr node = malloc(sizeof(NodePtr));
node->data = value;
node->next = NULL;

// find the position of key
NodePtr currPtr = head;
while (currPtr != NULL && currPtr->data != key) {
currPtr = currPtr->next;
}

// if key is not there, raise error
if (currPtr == NULL) {
printf("%s", "key not found");
} else if (currPtr->next == NULL) {
// if key is the last node, insert right after it
currPtr->next = node;
} else {
// insert between key and item next to key
NodePtr nextPtr = currPtr->next;
currPtr->next = node;
node->next = nextPtr;
}
}

// returns the data at first node
int topFront() {
if (isEmpty()) {
printf("%s", "List is empty");
} else {
return head->data;
}
}

// returns the data at last node
int topBack() {
if (isEmpty()) {
printf("%s", "List is empty");
} else if (head->next == NULL) {
return head->data;
} else {
NodePtr currPtr = head;
while (currPtr->next != NULL) {
currPtr = currPtr->next;
}
return currPtr->data;
}
}

// removes the item at front of the linked list and return
int popFront() {
int item;
if (isEmpty()) {
printf("%s", "List is empty");
return -99999;
} else {
NodePtr nextPtr = head->next;
item = head->data;
// remove head
free(head);

// make nextptr head
head = nextPtr;

}

return item;
}

// remove the item at the list of the linked list and return
int popBack() {
int item;
if (isEmpty()) {
printf("%s", "List is empty");
return -99999;
} else if (head->next == NULL) {
item = head->data;
free(head);
head = NULL;
} else {
NodePtr currPtr = head;
NodePtr prevPtr = NULL;
while (currPtr->next != NULL) {
prevPtr = currPtr;
currPtr = currPtr->next;
}
item = currPtr->data;
free(currPtr);
currPtr = NULL;
prevPtr->next = NULL;
}

return item;
}

// removes an item with value 'key'
void delete(int key) {
if (isEmpty()) {
printf("%s", "List is empty");
return;
}

// get to the position of key
NodePtr prevPtr = NULL;
NodePtr currPtr = head;
while(currPtr != NULL && currPtr->data != key) {
prevPtr = currPtr;
currPtr = currPtr->next;
}

if (currPtr == NULL) {
printf("%s", "Key is not found in the list");
return;
}

if (prevPtr == NULL) {
// this is the first item
head = head->next;
free(currPtr);
currPtr = NULL;
return;
}

if (currPtr->next == NULL) {
// this is the last item
prevPtr->next = NULL;
free(currPtr);
currPtr = NULL;
} else {
// anywhere in between first and last
NodePtr nextPtr = currPtr->next;
prevPtr->next = nextPtr;
free(currPtr);
currPtr = NULL;
}
}

// print the linked list
void print() {
NodePtr currPtr = head;
while (currPtr != NULL) {
printf("%d", currPtr->data);
printf(" ");
currPtr = currPtr->next;
}
printf("\n");
}

// check if a key is in the list
int find(int key) {
if (isEmpty()) {
return 0;
}

NodePtr currPtr = head;
while (currPtr != NULL && currPtr->data != key) {
currPtr = currPtr->next;
}

if (currPtr == NULL) {
return 0;
}

return 1;
}

int main() {
insertAtFront(23);
insertAtFront(24);
insertAtBack(25);
insertAfter(24, 55);
print();
// operations
return 0;
}
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
// C++ implementation of singly linked list
#include <iostream>

using namespace std;

// data structure for Node
// data -> the actual value
// next -> address of the next node
struct Node {
int data;
Node *next;
};

typedef Node *NodePtr;

class MyLinkedList {
private:
NodePtr head;

public:
MyLinkedList() {
head = nullptr;
}

// Insert 'value' at the front of the list
void insertAtFront(int value) {
NodePtr node = new Node;
node->data = value;
node->next = nullptr;

if (isEmpty()) {
head = node;
} else {
node->next = head;
head = node;
}
}

// insert value at the back of the linked list
void insertAtBack(int value) {
NodePtr node = new Node;
node->data = value;
node->next = nullptr;

if (isEmpty()) {
head = node;
} else {
// find the last node
NodePtr currPtr = head;
while (currPtr->next != nullptr) {
currPtr = currPtr->next;
}

// insert it
currPtr->next = node;
}
}

// inserts value after key
void insertAfter(int key, int value) {
NodePtr node = new Node;
node->data = value;
node->next = nullptr;

// find the position of key
NodePtr currPtr = head;
while (currPtr != nullptr && currPtr->data != key) {
currPtr = currPtr->next;
}

// if key is not there, raise error
if (currPtr == nullptr) {
cout<<"key not found";
} else if (currPtr->next == nullptr) {
// if key is the last node, insert right after it
currPtr->next = node;
} else {
// insert between key and item next to key
NodePtr nextPtr = currPtr->next;
currPtr->next = node;
node->next = nextPtr;
}
}

// returns the data at first node
int topFront() {
if (isEmpty()) {
cout<<"List is empty"<<endl;
} else {
return head->data;
}
}

// returns the data at last node
int topBack() {
if (isEmpty()) {
cout<<"List is empty"<<endl;
} else if (head->next == nullptr) {
return head->data;
} else {
NodePtr currPtr = head;
while (currPtr->next != nullptr) {
currPtr = currPtr->next;
}
return currPtr->data;
}
}

// removes the item at front of the linked list and return
int popFront() {
int item;
if (isEmpty()) {
cout<<"List is empty"<<endl;
return -99999;
} else {
NodePtr nextPtr = head->next;
item = head->data;
// remove head
delete head;

// make nextptr head
head = nextPtr;

}

return item;
}

// remove the item at the list of the linked list and return
int popBack() {
int item;
if (isEmpty()) {
cout<<"List if empty"<<endl;
return -99999;
} else if (head->next == nullptr) {
item = head->data;
delete head;
head = nullptr;
} else {
NodePtr currPtr = head;
NodePtr prevPtr = nullptr;
while (currPtr->next != nullptr) {
prevPtr = currPtr;
currPtr = currPtr->next;
}
item = currPtr->data;
delete currPtr;
currPtr = nullptr;
prevPtr->next = nullptr;
}

return item;
}

// removes an item with value 'key'
void remove(int key) {
if (isEmpty()) {
cout<<"list is empty"<<endl;
return;
}

// get to the position of key
NodePtr prevPtr = nullptr;
NodePtr currPtr = head;
while(currPtr != nullptr && currPtr->data != key) {
prevPtr = currPtr;
currPtr = currPtr->next;
}

if (currPtr == nullptr) {
cout<<"Key is not found in the list"<<endl;
return;
}

if (prevPtr == nullptr) {
// this is the first item
head = head->next;
delete currPtr;
currPtr = nullptr;
return;
}

if (currPtr->next == nullptr) {
// this is the last item
prevPtr->next = nullptr;
delete currPtr;
currPtr = nullptr;
} else {
// anywhere in between first and last
NodePtr nextPtr = currPtr->next;
prevPtr->next = nextPtr;
delete currPtr;
currPtr = nullptr;
}
}

// print the linked list
void print() {
NodePtr currPtr = head;
while (currPtr != nullptr) {
cout<<currPtr->data<<" ";
currPtr = currPtr->next;
}
cout<<endl;
}

// check if the list is empty
bool isEmpty() {
return head == nullptr;
}

// check if a key is in the list
bool find(int key) {
if (isEmpty()) {
return false;
}

NodePtr currPtr = head;
while (currPtr != nullptr && currPtr->data != key) {
currPtr = currPtr->next;
}

if (currPtr == nullptr) {
return false;
}

return true;
}
};

int main() {
MyLinkedList list;
// operations
return 0;
}
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
// Java implementation of Singly linked list 

class Node {
int data;
Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

public class MyLinkedList {
private Node head;

public MyLinkedList() {
head = null;
}

// Insert 'value' at the front of the list
public void insertAtFront(int value) {
Node node = new Node(value);
if(isEmpty()) {
head = node;
} else {
node.next = head;
head = node;
}
}

// insert value at the back of the linked list
public void insertAtBack(int value) {
Node node = new Node(value);
if (isEmpty()) {
head = node;
} else {
Node curr = head;
while(null != curr.next) {
curr = curr.next;
}

curr.next = node;
}
}

// inserts value after key
public void insertAfter(int key, int value) {
Node node = new Node(value);

// find the position of key
Node curr = head;
while(null != curr && curr.data != key) {
curr = curr.next;
}

if (null == curr) {
System.out.println("Key not found");
return;
}

if(null == curr.next) {
curr.next = node;
} else {
Node next = curr.next;
curr.next = node;
node.next = next;
}
}

// returns the data at first node
public int topFront() {
if (isEmpty()) {
System.out.println("List is empty");
return -999999;
}

return head.data;
}

// returns the data at last node
public int topBack() {
if(isEmpty()) {
System.out.println("List is empty");
return -999999;
}

Node curr = head;
while(curr.next != null) {
curr = curr.next;
}

return curr.data;
}

// removes the item at front of the linked list and return
public int popFront() {
if (isEmpty()) {
System.out.println("List is empty");
return -999999;
}

Node next = head.next;
int item = head.data;
head = next;
return item;
}

// remove the item at the end of the list and return
public int popBack() {
if (isEmpty()) {
System.out.println("List is empty");
return -999999;
}

// get to the last node
Node curr = head;
Node prev = null;
while(curr.next != null) {
prev = curr;
curr = curr.next;
}

int item = curr.data;

if (prev == null) {
// the list has only one item
head = null;
} else {
prev.next = null;
curr = null;
}

return item;
}

// removes an item with value 'key'
public void remove(int key) {
if (isEmpty()) {
System.out.println("List is empty");
return;
}

// find the position of the key
Node curr = head;
Node prev = null;

while(curr != null && curr.data != key) {
prev = curr;
curr = curr.next;
}

if(curr == null) {
System.out.print("key not found");
return;
}

// if curr is head, delete the head
if (prev == null) {
head = head.next;
curr = null;
} else if (curr.next == null) { // if curr is last item
prev.next = null;
curr = null;
} else { //anywhere between first and last node
Node next = curr.next;
prev.next = next;
curr = null;
}


}

// check if the key is in the list
public boolean find(int key) {
if (isEmpty()) {
System.out.println("List is empty");
return false;
}

Node curr = head;
while(curr != null && curr.data != key) {
curr = curr.next;
}

if (curr == null) {
return false;
}

return true;
}

// check if the list is empty
public boolean isEmpty() {
return head == null;
}

// print all the items
public void print() {
if (isEmpty()) {
System.out.println("Nothing to display");
} else {
Node curr = head;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}

public static void main(String [] args) {
MyLinkedList list = new MyLinkedList();
}
}
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
# Python implementation of Singly linked list 
import sys

class Node:
def __init__(self, data):
self.data = data
self.next = None

class MyLinkedList:
def __init__(self):
self.head = None

# Insert 'value' at the front of the list
def insert_at_front(self, value):
node = Node(value)
if self.is_empty():
self.head = node
else:
node.next = self.head
self.head = node

# insert value at the back of the linked list
def insert_at_back(self, value):
node = Node(value)
if self.is_empty():
self.head = node
else:
curr = self.head
while curr.next != None:
curr = curr.next
curr.next = node

# inserts value after key
def insert_after(self, key, value):
node = Node(value)

# find the position of key
curr = self.head
while curr != None and curr.data != key:
curr = curr.next

if curr == None:
print 'Key not found'
return

if curr.next == None:
curr.next = node
else:
next_node = curr.next
curr.next = node
node.next = next_node

# returns the data at first node
def top_front(self):
if self.is_empty():
print 'List is empty'
return

return self.head.data

# returns the data at last node
def top_back(self):
if self.is_empty():
print 'List is empty'
return

curr = self.head
while curr.next != None:
curr = curr.next

return curr.data

# removes the item at front of the linked list and return
def pop_front(self):
if self.is_empty():
print 'List is empty'
return

next_node = self.head.next
item = self.head.data
self.head = next_node
return item

# remove the item at the end of the list and return
def pop_back(self):
if self.is_empty():
print 'List is empty'
return

# get to the last node
curr = self.head
prev = None

while curr.next != None:
prev = curr
curr = curr.next

item = curr.data

if prev == None:
# the list has only one item
self.head = None
else:
prev.next = None
curr = None

return item

# removes an item with value 'key'
def remove(self, key):
if self.is_empty():
print 'List is empty'
return

# find the position of the key
curr = self.head
prev = None

while curr != None and curr.data != key:
prev = curr
curr = curr.next

if curr == None:
print 'key not found'
return

# if curr is head, delete the head
if prev == None:
self.head = self.head.next
curr = None
elif curr.next == None: # if curr is last item
prev.next = None
curr = None
else: #anywhere between first and last node
next_node = curr.next
prev.next = next_node
curr = None

# check if the key is in the list
def find(self, key):
if self.is_empty():
print 'List is empty'
return False

curr = self.head
while curr != None and curr.data != key:
curr = curr.next

if curr == None:
return False

return True

# check if the list is empty
def is_empty(self):
return self.head == None

# print all the items
def printlist(self):
if self.is_empty():
print "Nothing to display"
else:
curr = self.head
while (curr != None):
sys.stdout.write(str(curr.data) + ' ')
curr = curr.next

print ''

if __name__ == '__main__':
list = MyLinkedList()
# write code