clickHere
Updated on Mar 24, 2022 16:50 IST

There are three types of Linked Lists used daily by Engineers, and the most popular of the lot is the Singly Linked Lists. Singly Linked Lists traverse in a single direction, and each node has the data and the pointer to the next node. In this article, let us understand the depths of Singly Linked Lists in the following order:

## What is Singly Linked List

Singly Linked Lists are the simplest of the lot, where every node contains some data and a pointer to the next node of the same data type. So, every node stores the address to the next node in the sequence.

Here, you have to remember that Singly Linked Lists only allow the traversal of data in a single direction.

## Representation of Singly Linked Lists

A linked list is a chain of nodes, and each node has the following parts:

• Data Item

Node is represented in the C programming language as follows:

```struct node
{
int d;
struct node *n;
};```

Node is represented in Python programming language as follows:

```class node:
def __init__(self, d):
self.d = d
self.n = None```

### Traversal

Traversal refers to accessing elements in the list and displaying them as output.

To traverse through the list, you have to keep moving the temp node to the next node until the temp is NULL. As soon as temp = NULL, it implies that you have reached the end of the list

//Travseral code in C

```void DisplayList(struct node* node) {
while (node != NULL) {
printf(" %d ", node->d);
node = node->n;
}
}```

//Traversal code in Python

``` #Traverse the List
def DisplayList(self):
while (temp):
print(temp.d)
temp = temp.n```

### Insertion

There are three ways to insert an element in Singly Linked Lists.

Note: For all the types of insertion, you have to allocate memory and store data for a new node

• Insert at the beginning
•  Change the next of new node to point to head
•  Change the head to point to the newly created node

//Insertion code in C

```void InserBeg(struct node** head_ref, int new_d) {
struct node* node1 = (struct node*)malloc(sizeof(struct node));

node1->d = new_d;
}```

//Insertion code in Python

```# Insert at the beginning
def InserBeg(self, new_d):
newnode = node(new_d)

• Insert at the midpoint/ after a node
• Go to the node just before the required position of the new node
• Change the next pointer to include a new node

//Insertion code in C

```// Insert a node after a node
void InserAf(struct node* p, int new_d) {
if (p == NULL) {
printf("Previous node must not be  NULL");
return;
}

struct node* node1 = (struct node*)malloc(sizeof(struct node));
node1->d = new_d;
node1->n = p->n;
p->n = node1;
}```

//Insertion code in Python

```# Insert after a node
def InserAf(self, p, new_d):

if p is None:
print("The node must be present in Linked List.")
return

newnode = node(new_d)
newnode.n = p.n
p.n = newnode```
• Insert at the end
• Go to the last node and change the next of the last node to the recently created node

//Insertion code in C

```// Insert the the end
void InserEnd(struct node** head_ref, int new_d) {
struct node* node1 = (struct node*)malloc(sizeof(struct node));

node1->d = new_d;
node1->n = NULL;

return;
}

while (end->n != NULL) end = end->n;

end->n = node1;
return;
}```

//Insertion code in Python

```# Insert at the end
def InserEnd(self, new_d):
newnode = node(new_d)

return

while (end.n):
end = end.n

end.n = newnode```

### Deletion

There are three ways to delete elements in Singly Linked Lists.

• To delete from the beginning, you have to point the head to the second element
• To delete after a node, you have to go to the element, before the one that has to be deleted and exclude the same by changing the next pointers.
• To delete from the end, you have to go to the second last element and change its next to NULL.

Here, since you have to traverse through the entire list to delete an element, you have to

• Write the code to delete the node containing the key element which needs to be deleted.
• Include an if else loop for a case where the element to be deleted is not found in the List.

//Deletion in C

```// Delete a node
void DelNode(struct node** head_ref, int key) {
struct node *temp = *head_ref, *prev;

if (temp != NULL && temp->d == key) {
free(temp);
return;
}
while (temp != NULL && temp->d != key) {
prev = temp;
temp = temp->n;
}
if (temp == NULL) return;
prev->n = temp->n;

free(temp);
}```

//Deletion code in Python

``` # Deleting a node
def DelNode(self, index):

return

if index == 0:
temp = None
return
for i in range(index - 1):
temp = temp.n
if temp is None:
break
if temp is None:
return

if temp.n is None:
return

n = temp.n.n

temp.n = None

temp.n = n```

### Searching

Let us consider you have to search for an “key” element in the Linked Lists. Now to find this item, you have to

• Make HEAD as the current node and run the loop until the current node is NULL.
• In every iteration, you have to check if the value of the node = item. If YES, then return that item is found else continue the loop.

//Searching in C

```// Search an element
int FindElement(struct node** head_ref, int key) {

while (current != NULL) {
if (current->d == key) return 1;
current = current->n;
}
return 0;
}```

//Searching in Python

```# Search an element in Linked List
def FindElement(self, key):

while current is not None:
if current.d == key:
return True

current = current.n

return False```

### Sorting

Let us consider that you wish to sort the elements in ascending order. Then follow the below steps to execute the same:

1. Make HEAD as current node
2. Create another node “newnode” for later use
3. If HEAD is NULL then return
4. Else execute the loop until you reach NULL
5. For every iteration, you have to
6. Store the next node of current in “newnode”
7. Check if data of current node > next node. If YES, swap current node & newnode.

//Sorting in C

```// Sort the linked list
struct node *current = *head_ref, *index = NULL;
int temp;

return;
} else {
while (current != NULL) {
index = current->n;

while (index != NULL) {
if (current->d > index->d) {
temp = current->d;
current->d = index->d;
index->d = temp;
}
index = index->n;
}
current = current->n;
}
}
}```

//Sorting in Python

```# Sort the linked list
index = node(None)

return
else:
while current is not None:
# index points to the node n to current
index = current.n

while index is not None:
if current.d > index.d:
current.d, index.d = index.d, current.d

index = index.n
current = current.n```

## Singly Linked Lists in C

Refer to the following code to understand how to create a Singly Linked Lists and perform various operations in C.

```#include <stdio.h>
#include <stdlib.h>

// Create a node
struct node {
int d;
struct node* n;
};

void DisplayList(struct node* node) {
while (node != NULL) {
printf(" %d ", node->d);
node = node->n;
}
}

// Insert at the beginning
void InserBeg(struct node** head_ref, int new_d) {
struct node* node1 = (struct node*)malloc(sizeof(struct node));

node1->d = new_d;
}

// Insert a node after a node
void InserAf(struct node* p, int new_d) {
if (p == NULL) {
printf("Previous node must not be NULL");
return;
}

struct node* node1 = (struct node*)malloc(sizeof(struct node));
node1->d = new_d;
node1->n = p->n;
p->n = node1;
}

// Insert the the end
void InserEnd(struct node** head_ref, int new_d) {
struct node* node1 = (struct node*)malloc(sizeof(struct node));

node1->d = new_d;
node1->n = NULL;

return;
}

while (end->n != NULL) end = end->n;

end->n = node1;
return;
}

// Delete a node
void DelNode(struct node** head_ref, int key) {
struct node *temp = *head_ref, *prev;

if (temp != NULL && temp->d == key) {
free(temp);
return;
}
while (temp != NULL && temp->d != key) {
prev = temp;
temp = temp->n;
}

if (temp == NULL) return;
prev->n = temp->n;

free(temp);
}

// Search an element
int FindElement(struct node** head_ref, int key) {

while (current != NULL) {
if (current->d == key) return 1;
current = current->n;
}
return 0;
}

struct node *current = *head_ref, *index = NULL;
int temp;

return;
} else {
while (current != NULL) {
index = current->n;

while (index != NULL) {
if (current->d > index->d) {
temp = current->d;
current->d = index->d;
index->d = temp;
}
index = index->n;
}
current = current->n;
}
}
}

int main() {

printf("Linked List after inserting elements :
");

printf("
");

int item = 85;
printf("
The element %d is found", item);
} else {
printf("
}
printf("
");

printf("
Linked List after deleting element at node 4 :
");

printf("
");
printf("
Linked List after sorting in ascending order :
");
}```

## Singly Linked List in Python

Refer to the following code to understand how to create a Singly Linked Lists and perform various operations in Python.

```# Create a node
class node:
def __init__(self, d):
self.d = d
self.n = None

def __init__(self):

#Traverse the List
def DisplayList(self):
while (temp):
print(temp.d)
temp = temp.n

# Insert at the beginning
def InserBeg(self, new_d):
newnode = node(new_d)

# Insert after a node
def InserAf(self, p, new_d):

if p is None:
print("The given p node must in LinkedList.")
return

newnode = node(new_d)
newnode.n = p.n
p.n = newnode

# Insert at the end
def InserEnd(self, new_d):
newnode = node(new_d)

return

while (end.n):
end = end.n

end.n = newnode

# Deleting a node
def DelNode(self, index):

return

if index == 0:
temp = None
return
for i in range(index - 1):
temp = temp.n
if temp is None:
break
if temp is None:
return

if temp.n is None:
return

n = temp.n.n

temp.n = None

temp.n = n

# Search an element in Linked List
def FindElement(self, key):

while current is not None:
if current.d == key:
return True

current = current.n

return False

index = node(None)

return
else:
while current is not None:
# index points to the node n to current
index = current.n

while index is not None:
if current.d > index.d:
current.d, index.d = index.d, current.d

index = index.n
current = current.n

if __name__ == '__main__':
#Start the Linked List as empty elements
#Insert elements
llist.InserBeg(31)
llist.InserEnd(19)
llist.InserBeg(62)
llist.InserEnd(12)
llist.InserEnd(85)

print('Linked List after inserting elements :')
llist.DisplayList()

#Search for elements
print()
item = 85
if llist.FindElement(item):
print("
The element " + str(item) + " is found")
else:
print("

#Delete elements
print("
Linked List after deleting element at node '4'")
llist.DelNode(4)
llist.DisplayList()

#sort in ascending order
print("
Linked List after sorting in ascending order : ")
llist.DisplayList()```

#### Output:

Time Complexity

Space Complexity of Linked List is O(n).

With this, we end this article on Singly Linked List and how to implement it. We hope you found it informative.

Top Trending Tech Articles:
Career Opportunities after BTech | Online Python Compiler | What is Coding | Queue Data Structure | Top Programming Language | Trending DevOps Tools | Highest Paid IT Jobs | Most In Demand IT Skills | Networking Interview Questions | Features of Java | Basic Linux Commands | Amazon Interview Questions

Recently completed any professional course/certification from the market? Tell us what liked or disliked in the course for more curated content.

clickHere

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio

## Trending Technology Courses Data Structures
Coursera 4.1 Data Structures and Performance
Coursera 4.5  Data Structures and Performance
Coursera 4.5Starts today  ## Top Picks & New Arrivals        