Singly Linked List in C/C++

Dhimas Arief Dharmawan

August 26, 2024

Concept of Singly Linked List

▶ A singly linked list is a data structure consisting of nodes.

▶ Each node contains:
▶ Data: The value stored in the node.
▶ Pointer: A pointer to the next node in the list.
▶ The last node points to NULL, indicating the end of the list.
▶ It allows for dynamic memory allocation and easy
insertion/deletion of nodes.
Node Structure

▶ Each node in the linked list is represented by a structure.

▶ The structure contains two parts:
▶ Data: An integer in this case, but it could be any data type.
▶ Next Pointer: A pointer to the next node in the list.

1 s t r u c t Node {
2 i n t data ;
3 s t r u c t Node∗ n e x t ;
4 };
Listing 1: Node Structure in C
Function to Create a New Node

▶ The ‘createNode‘ function dynamically allocates memory for a

new node.
▶ It initializes the node with the provided data and sets its
‘next‘ pointer to NULL.
▶ The function returns a pointer to the newly created node.
1 s t r u c t Node∗ c r e a t e N o d e ( i n t d a t a ) {
2 s t r u c t Node∗ newNode = ( s t r u c t Node ∗ ) m a l l o c ( s i z e o f (
s t r u c t Node ) ) ;
3 newNode−>d a t a = d a t a ;
4 newNode−>n e x t = NULL ;
5 r e t u r n newNode ;
6 }
Listing 2: Creating a New Node
Possible Operations on a Linked List
▶ Insertion
▶ At the beginning
▶ At the end
▶ After a specific node
▶ Deletion
▶ From the beginning
▶ From the end
▶ Specific node (by value)
▶ Traversal
▶ Searching
▶ Updating/Modifying Data
▶ Reversing the List
▶ Finding the Length of the List

Discussion Prompt:
▶ Discuss how each of these operations can be implemented in a
singly linked list.
▶ Consider the complexity and edge cases for each operation.
Insertion at the Beginning

▶ The ‘insertAtBeginning‘ function inserts a new node at the

start of the list.
▶ The ‘next‘ pointer of the new node is set to the current head
of the list.
▶ The head of the list is updated to point to the new node.
Insertion at the Beginning (contd.)

1 v o i d i n s e r t A t B e g i n n i n g ( s t r u c t Node ∗∗ head , i n t d a t a ) {
2 s t r u c t Node∗ newNode = c r e a t e N o d e ( d a t a ) ;
3 newNode−>n e x t = ∗ head ;
4 ∗ head = newNode ;
5 }
Listing 3: Inserting at the Beginning
Insertion at the End

▶ The ‘insertAtEnd‘ function adds a new node to the end of the

list.
▶ If the list is empty, the new node becomes the head.
▶ Otherwise, the function traverses to the end of the list and
sets the ‘next‘ pointer of the last node to the new node.
Insertion at the End (contd.)

1 v o i d i n s e r t A t E n d ( s t r u c t Node ∗∗ head , i n t d a t a ) {
2 s t r u c t Node∗ newNode = c r e a t e N o d e ( d a t a ) ;
3 i f ( ∗ head == NULL) {
4 ∗ head = newNode ;
5 return ;
6 }
7 s t r u c t Node∗ temp = ∗ head ;
8 w h i l e ( temp−>n e x t != NULL) {
9 temp = temp−>n e x t ;
10 }
11 temp−>n e x t = newNode ;
12 }
Listing 4: Inserting at the End
Insertion After a Specific Node

▶ The ‘insertAfterNode‘ function inserts a new node after a

specific node in the list.
▶ It is useful for inserting elements in between the list.
Insertion After a Specific Node

1 v o i d i n s e r t A f t e r N o d e ( s t r u c t Node∗ prevNode , i n t d a t a ) {
2 i f ( prev Node == NULL) {
3 p r i n t f ( ” P r e v i o u s node c a n n o t be NULL . \ n” ) ;
4 return ;
5 }
6 s t r u c t Node∗ newNode = c r e a t e N o d e ( d a t a ) ;
7 newNode−>n e x t = prevNode−>n e x t ;
8 prevNode−>n e x t = newNode ;
9 }
Listing 5: Inserting After a Specific Node
Deleting a Node by Value

▶ The ‘deleteNode‘ function removes a node with a specific

value from the list.
▶ It updates the ‘next‘ pointer of the previous node to skip the
deleted node.
Deleting a Node by Value (contd.)
1 v o i d d e l e t e N o d e ( s t r u c t Node ∗∗ head , i n t k e y ) {
2 s t r u c t Node∗ temp = ∗ head ;
3 s t r u c t Node∗ p r e v = NULL ;
4
5 i f ( temp != NULL && temp−>d a t a == k e y ) {
6 ∗ head = temp−>n e x t ;
7 f r e e ( temp ) ;
8 return ;
9 }
10
11 w h i l e ( temp != NULL && temp−>d a t a != k e y ) {
12 p r e v = temp ;
13 temp = temp−>n e x t ;
14 }
15
16 i f ( temp == NULL) r e t u r n ;
17
18 p r e v −>n e x t = temp−>n e x t ;
19 f r e e ( temp ) ;
20 }
Listing 6: Deleting a Node by Value
Deleting the First Node

▶ The ‘deleteFromBeginning‘ function removes the first node of

the linked list.
▶ The head is updated to point to the second node, and the
first node is freed.
Deleting the First Node (contd.)

1 v o i d d e l e t e F r o m B e g i n n i n g ( s t r u c t Node ∗∗ head ) {
2 i f ( ∗ head == NULL) {
3 p r i n t f ( ”The l i s t i s empty . \ n” ) ;
4 return ;
5 }
6 s t r u c t Node∗ temp = ∗ head ;
7 ∗ head = ( ∗ head )−>n e x t ;
8 f r e e ( temp ) ;
9 }
Listing 7: Deleting the First Node
Deleting the Last Node

▶ The ‘deleteFromEnd‘ function removes the last node of the

linked list.
▶ It traverses to the second-to-last node and sets its ‘next‘
pointer to NULL.
Deleting the Last Node (contd.)
1 v o i d d e l e t e F r o m E n d ( s t r u c t Node ∗∗ head ) {
2 i f ( ∗ head == NULL) {
3 p r i n t f ( ”The l i s t i s empty . \ n” ) ;
4 return ;
5 }
6 s t r u c t Node∗ temp = ∗ head ;
7 s t r u c t Node∗ p r e v = NULL ;
8 w h i l e ( temp−>n e x t != NULL) {
9 p r e v = temp ;
10 temp = temp−>n e x t ;
11 }
12 i f ( p r e v != NULL) {
13 p r e v −>n e x t = NULL ;
14 } else {
15 ∗ head = NULL ;
16 }
17 f r e e ( temp ) ;
18 }
Listing 8: Deleting the Last Node
Printing the Linked List

▶ The ‘printList‘ function traverses the linked list and prints the
data in each node.
▶ It starts from the head and follows the ‘next‘ pointers until it
reaches a node with ‘next‘ pointing to NULL.
▶ The list is displayed in the format: ‘data1 -¿ data2 -¿ ... -¿
NULL‘.
Printing the Linked List (contd.)

1 v o i d p r i n t L i s t ( s t r u c t Node∗ head ) {
2 s t r u c t Node∗ temp = head ;
3 w h i l e ( temp != NULL) {
4 p r i n t f ( ”%d −> ” , temp−>d a t a ) ;
5 temp = temp−>n e x t ;
6 }
7 p r i n t f ( ”NULL\n” ) ;
8 }
Listing 9: Printing the List
Searching in the Linked List

▶ The ‘search‘ function looks for a node with a specific value in

the linked list.
▶ If found, it returns a pointer to the node; otherwise, it returns
NULL.
Searching in the Linked List (contd.)

1 s t r u c t Node∗ s e a r c h ( s t r u c t Node∗ head , i n t k e y ) {

2 s t r u c t Node∗ temp = head ;
3 w h i l e ( temp != NULL) {
4 i f ( temp−>d a t a == k e y ) {
5 r e t u r n temp ;
6 }
7 temp = temp−>n e x t ;
8 }
9 r e t u r n NULL ;
10 }
Listing 10: Searching in the List
Updating Node Data

▶ The ‘updateNode‘ function updates the data of a node with a

specific value.
▶ It first searches for the node and then updates the value if the
node is found.
Updating Node Data (contd.)

1 v o i d updateNode ( s t r u c t Node∗ head , i n t o l d D a t a , i n t

newData ) {
2 s t r u c t Node∗ temp = s e a r c h ( head , o l d D a t a ) ;
3 i f ( temp != NULL) {
4 temp−>d a t a = newData ;
5 } else {
6 p r i n t f ( ”Node w i t h d a t a %d n o t f o u n d . \ n” ,
oldData ) ;
7 }
8 }
Listing 11: Updating Node Data
Reversing the Linked List

▶ Many algorithms require reversing the list as a preprocessing

or intermediate step. For example, in certain problems
involving linked lists, such as adding two numbers represented
by linked lists, reversing the list simplifies the logic.
▶ Easier traversal for certain tasks: If you need to traverse a list
from the end to the beginning, reversing the list first can
make the process more straightforward, especially in recursive
solutions.
▶ The ‘reverseList‘ function reverses the linked list so that the
last node becomes the head and vice versa.
▶ It uses three pointers: ‘prev‘, ‘current‘, and ‘next‘ to reverse
the direction of the ‘next‘ pointers.
Reversing the Linked List

1 v o i d r e v e r s e L i s t ( s t r u c t Node ∗∗ head ) {
2 s t r u c t Node∗ p r e v = NULL ;
3 s t r u c t Node∗ c u r r e n t = ∗ head ;
4 s t r u c t Node∗ n e x t = NULL ;
5 w h i l e ( c u r r e n t != NULL) {
6 n e x t = c u r r e n t −>n e x t ;
7 c u r r e n t −>n e x t = p r e v ;
8 prev = current ;
9 current = next ;
10 }
11 ∗ head = p r e v ;
12 }
Listing 12: Reversing the List
Finding the Length of the List

▶ The ‘getLength‘ function counts the number of nodes in the

linked list.
▶ It traverses the entire list and increments a counter for each
node.
Finding the Length of the List (contd.)

1 i n t g e t L e n g t h ( s t r u c t Node∗ head ) {
2 int length = 0;
3 s t r u c t Node∗ temp = head ;
4 w h i l e ( temp != NULL) {
5 l e n g t h ++;
6 temp = temp−>n e x t ;
7 }
8 return length ;
9 }
Listing 13: Finding the Length of the List