What is the minimum number of pointers that may have to modified for an insertion operation in singly linked list?

ISRO | ISRO CS 2017 – May | Question 79

Circular Singly Linked List | Insertion

We have discussed Singly and Circular Linked List in the following post:
Singly Linked List
Circular Linked List

Why Circular? In a singly linked list, for accessing any node of the linked list, we start traversing from the first node. If we are at any node in the middle of the list, then it is not possible to access nodes that precede the given node. This problem can be solved by slightly altering the structure of a singly linked list. In a singly linked list, the next part (pointer to next node) is NULL. If we utilize this link to point to the first node, then we can reach the preceding nodes. Refer to this for more advantages of circular linked lists.
The structure thus formed is a circular singly linked list and looks like this:

In this post, the implementation and insertion of a node in a Circular Linked List using a singly linked list are explained.

Implementation
To implement a circular singly linked list, we take an external pointer that points to the last node of the list. If we have a pointer last pointing to the last node, then last -> next will point to the first node.

The pointer last points to node Z and last -> next points to node P.

Why have we taken a pointer that points to the last node instead of the first node?
For the insertion of a node at the beginning, we need to traverse the whole list. Also, for insertion at the end, the whole list has to be traversed. If instead of start pointer, we take a pointer to the last node, then in both cases there won’t be any need to traverse the whole list. So insertion at the beginning or at the end takes constant time, irrespective of the length of the list.

Insertion
A node can be added in three ways:

• Insertion in an empty list
• Insertion at the beginning of the list
• Insertion at the end of the list
• Insertion in between the nodes

Insertion in an empty List
Initially, when the list is empty, the last pointer will be NULL.

After inserting node T,

After insertion, T is the last node, so the pointer last points to node T. And Node T is the first and the last node, so T points to itself.
Function to insert a node into an empty list,

C++

struct Node *addToEmpty(struct Node *last, int data) { // This function is only for empty list if (last != NULL) return last; // Creating a node dynamically. struct Node *temp = (struct Node*)malloc(sizeof(struct Node)); // Assigning the data. temp -> data = data; last = temp; // Note : list was empty. We link single node // to itself. temp -> next = last; return last; }

Java

static Node addToEmpty(Node last, int data) { // This function is only for empty list if (last != null) return last; // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; last = temp; // Note : list was empty. We link single node // to itself. temp.next = last; return last; } // This code is contributed by gauravrajput1

Python3

# This function is only for empty list def addToEmpty(self, data): if (self.last != None): return self.last # Creating the newnode temp temp = Node(data) self.last = temp # Creating the link self.last.next = self.last return self.last # this code is contributed by shivanisinghss2110

C#

static Node addToEmpty(Node last, int data) { // This function is only for empty list if (last != null) return last; // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; last = temp; // Note : list was empty. We link single node // to itself. temp.next = last; return last; } // This code contributed by umadevi9616

Javascript

<script> function addToEmpty(last , data) { // This function is only for empty list if (last != null) return last; // Creating a node dynamically. var temp = new Node(); // Assigning the data. temp.data = data; last = temp; // Note : list was empty. We link single node // to itself. temp.next = last; return last; } // This code contributed by umadevi9616 </script>

Insertion at the beginning of the list
To insert a node at the beginning of the list, follow these steps:
1. Create a node, say T.
2. Make T -> next = last -> next.
3. last -> next = T.

After insertion,

Function to insert nodes at the beginning of the list,

C++

struct Node *addBegin(struct Node *last, int data) { if (last == NULL) return addToEmpty(last, data); // Creating a node dynamically. struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); // Assigning the data. temp -> data = data; // Adjusting the links. temp -> next = last -> next; last -> next = temp; return last; }

Java

static Node addBegin(Node last, int data) { if (last == null) return addToEmpty(last, data); // Creating a node dynamically Node temp = new Node(); // Assigning the data temp.data = data; // Adjusting the links temp.next = last.next; last.next = temp; return last; } // This code is contributed by rutvik_56

Python3

def addBegin(self, data): if (self.last == None): return self.addToEmpty(data) temp = Node(data) temp.next = self.last.next self.last.next = temp return self.last # this code is contributed by shivanisinghss2110

C#

static Node addBegin(Node last, int data) { if (last == null) return addToEmpty(last, data); // Creating a node dynamically Node temp = new Node(); // Assigning the data temp.data = data; // Adjusting the links temp.next = last.next; last.next = temp; return last; } // This code is contributed by Pratham76

Javascript

<script> function addBegin(last , data) { if (last == null) return addToEmpty(last, data); // Creating a node dynamically. var temp = new Node(); // Assigning the data. temp.data = data; // Adjusting the links. temp.next = last.next; last.next = temp; return last; } // This code contributed by Shivani </script>

Insertion at the end of the list
To insert a node at the end of the list, follow these steps:
1. Create a node, say T.
2. Make T -> next = last -> next;
3. last -> next = T.
4. last = T.

After insertion,

Function to insert a node at the end of the List

C++

struct Node *addEnd(struct Node *last, int data) { if (last == NULL) return addToEmpty(last, data); // Creating a node dynamically. struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); // Assigning the data. temp -> data = data; // Adjusting the links. temp -> next = last -> next; last -> next = temp; last = temp; return last; }

Java

static Node addEnd(Node last, int data) { if (last == null) return addToEmpty(last, data); // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; // Adjusting the links. temp.next = last.next; last.next = temp; last = temp; return last; } // This code is contributed by shivanisinghss2110

Python3

def addEnd(self, data): if (self.last == None): return self.addToEmpty(data) # Assigning the data. temp = Node(data) # Adjusting the links. temp.next = self.last.next self.last.next = temp self.last = temp return self.last # This code is contributed by shivanisinghss2110

C#

static Node addEnd(Node last, int data) { if (last == null) return addToEmpty(last, data); // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; // Adjusting the links. temp.next = last.next; last.next = temp; last = temp; return last; } // This code is contributed by shivanisinghss2110

Javascript

<script> function addEnd(last, data) { if (last == null) return addToEmpty(last, data); var temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; last = temp; return last; } // this code is contributed by shivanisinghss2110 </script>

Insertion in between the nodes
To insert a node in between the two nodes, follow these steps:
1. Create a node, say T.
2. Search for the node after which T needs to be inserted, say that node is P.
3. Make T -> next = P -> next;
4. P -> next = T.
Suppose 12 needs to be inserted after the node has the value 10,

After searching and insertion,

Function to insert a node at the end of the List,

C++

struct Node *addAfter(struct Node *last, int data, int item) { if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; // Searching the item. do { if (p ->data == item) { // Creating a node dynamically. temp = (struct Node *)malloc(sizeof(struct Node)); // Assigning the data. temp -> data = data; // Adjusting the links. temp -> next = p -> next; // Adding newly allocated node after p. p -> next = temp; // Checking for the last node. if (p == last) last = temp; return last; } p = p -> next; } while (p != last -> next); cout << item << " not present in the list." << endl; return last; }

Java

static Node addAfter(Node last, int data, int item) { if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == item) { temp = new Node(); temp.data = data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; } while(p != last.next); System.out.println(item + " not present in the list."); return last; } // This code is contributed by shivanisinghss2110

Python3

def addAfter(self, data, item): if (self.last == None): return None temp = Node(data) p = self.last.next while p: if (p.data == item): temp.next = p.next p.next = temp if (p == self.last): self.last = temp return self.last else: return self.last p = p.next if (p == self.last.next): print(item, "not present in the list") break # This code is contributed by shivanisinghss2110

C#

static Node addAfter(Node last, int data, int item) { if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == item) { temp = new Node(); temp.data = data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; } while(p != last.next); Console.WriteLine(item + " not present in the list."); return last; } // This code is contributed by shivanisinghss2110

Javascript

<script> function addAfter(last, data, item) { if (last == null) return null; var temp, p; p = last.next; do { if (p.data == item) { temp = new Node(); temp.data = data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; } while (p != last.next); document.write(item + " not present in the list. <br>"); return last; } // This code is contributed by shivanisinghss2110 </script>

The following is a complete program that uses all of the above methods to create a circular singly linked list.

C++

#include<bits/stdc++.h> using namespace std; struct Node { int data; struct Node *next; }; struct Node *addToEmpty(struct Node *last, int data) { // This function is only for empty list if (last != NULL) return last; // Creating a node dynamically. struct Node *temp = (struct Node*)malloc(sizeof(struct Node)); // Assigning the data. temp -> data = data; last = temp; // Creating the link. last -> next = last; return last; } struct Node *addBegin(struct Node *last, int data) { if (last == NULL) return addToEmpty(last, data); struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = last -> next; last -> next = temp; return last; } struct Node *addEnd(struct Node *last, int data) { if (last == NULL) return addToEmpty(last, data); struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } struct Node *addAfter(struct Node *last, int data, int item) { if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == item) { temp = (struct Node *)malloc(sizeof(struct Node)); temp -> data = data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while(p != last -> next); cout << item << " not present in the list." << endl; return last; } void traverse(struct Node *last) { struct Node *p; // If list is empty, return. if (last == NULL) { cout << "List is empty." << endl; return; } // Pointing to first Node of the list. p = last -> next; // Traversing the list. do { cout << p -> data << " "; p = p -> next; } while(p != last->next); } // Driven Program int main() { struct Node *last = NULL; last = addToEmpty(last, 6); last = addBegin(last, 4); last = addBegin(last, 2); last = addEnd(last, 8); last = addEnd(last, 12); last = addAfter(last, 10, 8); traverse(last); return 0; }

Java

class GFG { static class Node { int data; Node next; }; static Node addToEmpty(Node last, int data) { // This function is only for empty list if (last != null) return last; // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; last = temp; // Creating the link. last.next = last; return last; } static Node addBegin(Node last, int data) { if (last == null) return addToEmpty(last, data); Node temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; return last; } static Node addEnd(Node last, int data) { if (last == null) return addToEmpty(last, data); Node temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; last = temp; return last; } static Node addAfter(Node last, int data, int item) { if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == item) { temp = new Node(); temp.data = data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; } while(p != last.next); System.out.println(item + " not present in the list."); return last; } static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println("List is empty."); return; } // Pointing to first Node of the list. p = last.next; // Traversing the list. do { System.out.print(p.data + " "); p = p.next; } while(p != last.next); } // Driven code public static void main(String[] args) { Node last = null; last = addToEmpty(last, 6); last = addBegin(last, 4); last = addBegin(last, 2); last = addEnd(last, 8); last = addEnd(last, 12); last = addAfter(last, 10, 8); traverse(last); } } /* This code contributed by PrinciRaj1992 */

Python3

class Node: def __init__(self, data): self.data = data self.next = None class CircularLinkedList: def __init__(self): self.last = None # This function is only for empty list def addToEmpty(self, data): if (self.last != None): return self.last # Creating the newnode temp temp = Node(data) self.last = temp # Creating the link self.last.next = self.last return self.last def addBegin(self, data): if (self.last == None): return self.addToEmpty(data) temp = Node(data) temp.next = self.last.next self.last.next = temp return self.last def addEnd(self, data): if (self.last == None): return self.addToEmpty(data) temp = Node(data) temp.next = self.last.next self.last.next = temp self.last = temp return self.last def addAfter(self, data, item): if (self.last == None): return None temp = Node(data) p = self.last.next while p: if (p.data == item): temp.next = p.next p.next = temp if (p == self.last): self.last = temp return self.last else: return self.last p = p.next if (p == self.last.next): print(item, "not present in the list") break def traverse(self): if (self.last == None): print("List is empty") return temp = self.last.next while temp: print(temp.data, end = " ") temp = temp.next if temp == self.last.next: break # Driver Code if __name__ == '__main__': llist = CircularLinkedList() last = llist.addToEmpty(6) last = llist.addBegin(4) last = llist.addBegin(2) last = llist.addEnd(8) last = llist.addEnd(12) last = llist.addAfter(10,8) llist.traverse() # This code is contributed by # Aditya Singh

C#

using System; public class GFG { public class Node { public int data; public Node next; }; static Node addToEmpty(Node last, int data) { // This function is only for empty list if (last != null) return last; // Creating a node dynamically. Node temp = new Node(); // Assigning the data. temp.data = data; last = temp; // Creating the link. last.next = last; return last; } static Node addBegin(Node last, int data) { if (last == null) return addToEmpty(last, data); Node temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; return last; } static Node addEnd(Node last, int data) { if (last == null) return addToEmpty(last, data); Node temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; last = temp; return last; } static Node addAfter(Node last, int data, int item) { if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == item) { temp = new Node(); temp.data = data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; } while(p != last.next); Console.WriteLine(item + " not present in the list."); return last; } static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { Console.WriteLine("List is empty."); return; } // Pointing to first Node of the list. p = last.next; // Traversing the list. do { Console.Write(p.data + " "); p = p.next; } while(p != last.next); } // Driven code public static void Main(String[] args) { Node last = null; last = addToEmpty(last, 6); last = addBegin(last, 4); last = addBegin(last, 2); last = addEnd(last, 8); last = addEnd(last, 12); last = addAfter(last, 10, 8); traverse(last); } } // This code contributed by Rajput-Ji

Javascript

<script> class Node { constructor() { this.data = 0; this.next = null; } } function addToEmpty(last, data) { // This function is only for empty list if (last != null) return last; // Creating a node dynamically. var temp = new Node(); // Assigning the data. temp.data = data; last = temp; // Creating the link. last.next = last; return last; } function addBegin(last, data) { if (last == null) return addToEmpty(last, data); var temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; return last; } function addEnd(last, data) { if (last == null) return addToEmpty(last, data); var temp = new Node(); temp.data = data; temp.next = last.next; last.next = temp; last = temp; return last; } function addAfter(last, data, item) { if (last == null) return null; var temp, p; p = last.next; do { if (p.data == item) { temp = new Node(); temp.data = data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; } while (p != last.next); document.write(item + " not present in the list. <br>"); return last; } function traverse(last) { var p; // If list is empty, return. if (last == null) { document.write("List is empty.<br>"); return; } // Pointing to first Node of the list. p = last.next; // Traversing the list. do { document.write(p.data + " "); p = p.next; } while (p != last.next); } // Driven code var last = null; last = addToEmpty(last, 6); last = addBegin(last, 4); last = addBegin(last, 2); last = addEnd(last, 8); last = addEnd(last, 12); last = addAfter(last, 10, 8); traverse(last); </script>

Output:

2 4 6 8 10 12

This article is contributed by Anuj Chauhan. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Article Tags :

Linked List

circular linked list

Practice Tags :

Linked List

circular linked list

Linked List Interview Questions

A list of top frequently asked Linked List Interview Questions and answers are given below.

1) Explain Linked List in short.

A linked list may be defined as a linear data structure which can store a collection of items. In another way, the linked list can be utilized to store various objects of similar types. Each element or unit of the list is indicated as a node. Each node contains its data and the address of the next node. It is similar to a chain. Linked lists are used to create graphs and trees.

2) How will you represent a linked list in a graphical view?

A linked list may be defined as a data structure in which each element is a separate object. Linked list elements are not kept at the contiguous location. The pointers are used to link the elements of the Linked List.

Each node available in a list is made up of two items- the data itself and a reference (also known as a link) to the next node in the sequence. The last node includes a reference to null. The starting point into a linked list is known as the head of the list. It should be noted that the head is a reference to the first node, not a separate node. The head is considered as a null reference if the list is empty.

3) How many types of Linked List exist?

There are multiple types of Linked Lists available:

• Singly Linked List
• Doubly Linked List
• Multiply Linked List
• Circular Linked List

4) Explain Singly Linked List in short.

The singly linked list includes nodes which contain a data field and next field. The next field further points to the next node in the line of nodes.

In other words, the nodes in singly linked lists contain a pointer to the next node in the list. We can perform operations like insertion, deletion, and traversal in singly linked lists.

A singly linked list is shown below whose nodes contain two fields: an integer value and a pointer value (a link to the next node).

5) What do you understand by Doubly Linked List?

The doubly linked list includes a pointer (link) to the next node as well as to the previous node in the list. The two links between the nodes may be called "forward" and "backward, "or "next" and "prev (previous)." A doubly linked list is shown below whose nodes consist of three fields: an integer value, a link that points to the next node, and a link that points to the previous node.

A technique (known as XOR-linking) is used to allow a doubly-linked list to be implemented with the help of a single link field in each node. However, this technique needs more ability to perform some operations on addresses, and therefore may not be available for some high-level languages.

Most of the modern operating systems use doubly linked lists to maintain references to active threads, processes, and other dynamic objects.

6) Explain Multiply Linked List in short.

In a multiply linked list, each node consists of two or more link fields. Each field is used to join the same set of records in a different order of the same set, e.g. "by name, by date of birth, by the department, etc.".

7) How will you explain Circular Linked List?

In the last node of a linked list, the link field often contains a null reference. Instead of including a null pointer at the end of the list, the last node in circular linked lists includes a pointer pointing to the first node. In such cases, the list is said to be ?circularly linked? otherwise it is said to be 'open' or 'linear.' A circular linked list is that type of list where the last pointer points or contains the address of the first node.

In case of a circular doubly linked list, the first node also points to the last node of the list.

8) How many pointers are necessary to implement a simple Linked List?

There are generally three types of pointers required to implement a simple linked list:

• A 'head' pointer which is used for pointing to the start of the record in a list.
• A 'tail' pointer which is used for pointing to the last node. The key factor in the last node is that its subsequent pointer points to nothing (NULL).
• A pointer in every node which is used for pointing to the next node element.

9) How can you represent a linked list node?

The simplest method to represent a linked list node is wrapping the data and the link using typedef structure. Then further assigning the structure as a Node pointer that points to the next node.

An example of representation in C can be defined as:

10) Which type of memory allocation is referred for Linked List?

Dynamic memory allocation is referred for Linked List.

11) What do you know about traversal in linked lists?

The term 'traversal' refers to the operation of processing each element present in the list.

12) What are the main differences between the Linked List and Linear Array?

13) What does the dummy header in the linked list contain?

In a linked list, the dummy header consists of the first record of the actual data.

14) Mention a few applications of Linked Lists?

Few of the main applications of Linked Lists are:

• Linked Lists let us implement queues, stacks, graphs, etc.
• Linked Lists let us insert elements at the beginning and end of the list.

15) How can you insert a node to the beginning of a singly linked list?

To insert the node to the beginning of the list, we need to follow these steps:

• Create a new node
• Insert new node by assigning the head pointer to the new node's next pointer
• Update the head pointer to point the new node

16) Name some applications which use Linked Lists.

Both queues and stacks can be implemented using a linked list. Some of the other applications that use linked list are a binary tree, skip, unrolled linked list, hash table, etc.

17) Differentiate between singly and doubly linked lists?

Doubly linked list nodes consist of three fields: an integer value and two links pointing to two other nodes (one to the last node and another to the next node).

On the other hand, a singly linked list consists of a link which points only to the next node.

18) What is the main advantage of a linked list?

The main advantage of a linked list is that we do not need to specify a fixed size for the list. The more elements we add to the chain, the bigger the chain gets.

19) How can someone add an item to the beginning of the list?

Adding an item to the beginning of the list, we need to follow the given steps:

• Create a new item and set up its value.
• Link the newly created item pointing to the head of the list.
• Set up the head of the list as our new item.

If we are using a function to do this operation, we need to alter the head variable.

20) How can someone insert a node at the end of Linked List?

This case is a little bit difficult as it depends upon the type of implementation. If we have a tail pointer, then it is simple. In case we do not have a tail pointer, we will have to traverse the list until we reach to the end (i.e., the next pointer is NULL). Then we need to create a new node and make that last node?s next pointer point to the new node.

21) How can someone insert a node in a random location of the Linked List?

If we want to insert a node in the first position or an empty list, we can insert the node easily. Otherwise, we need to traverse the list until we reach the specified position or at the end of the list. Then we can insert a new node. Inserting a node in the middle position is a little bit difficult as we have to make sure that we perform the pointer assignment in the correct order. To insert a new node in the middle, follow the steps:

• First, we need to set the new node's next pointer to that node which is present before it.
• Then we are required to assign a previous node's next pointer to the starting position of the new node.

Check the example below:

22) How can we delete the first node from the singly linked list?

To delete the first node from the singly linked list, we need to follow below steps:

• Copy the first node address to some temporary variable.
• Change the head to the second node of the linked list.
• Remove the connection of the first node to the second node.
• Delete temp and free up the memory occupied by the first node.

23) How can we delete any specific node from the linked list?

If a node that we want to delete is a root node, we can delete it easily. To delete a middle node, we must have a pointer pointing to that node which is present before the node that we want to delete. So if the position is non-zero, then we run a position loop and get a pointer to the previous node.

The steps given below are used to delete the node from the list at the specified position:

• Set up the head to point to that node which the head is pointing.
• Traverse the list to the desired position or till the end of the list (whichever comes first)
• We need to point the previous node to the next node.

24) How can we reverse a singly linked list?

To reverse the singly linked list, we are required to iterate through the list. We need to reverse the link at each step like after the first iteration, the head will point to null, and the next element will point to the head. At the end of traversal when we reach the tail of the linked list, the tail will start pointing to the second last element and will become a new head. It is because we can further traverse through all the elements from that particular node.

The steps given below can be used to reverse a singly linked list:

• First, we need to set a pointer (*current) pointing to the first node (i.e., current=head).
• Move ahead until current! =null (till the end of the list).
• Set another pointer (*next) pointing to the next node (i.e. next=current->next>next=result
• Keep reference of *next in a temporary variable (*result) i.e. current->next=result
• Exchange the result value with current, i.e., result=current
• And then swap the current value with next, I.e., current=next.
• Return result and repeat from step 2.

A linked list can also be reversed by using recursion which eliminates the use of a temporary variable.

25) How can we remove loops in a linked list? What are the functions of fast and slow pointers?

The main concept to detect and remove a loop in a linked list is to use two pointers (one slow pointer and a fast pointer). The slow pointer traverses single node at a time, whereas the fast pointer traverses twice as fast as the first one. If the linked list contains loop in it, the fast and slow pointer will be at the same node. On the other hand, if the list doesn't consist loop in it, obviously the fast pointer will reach the end before the slow pointer does. A loop is detected if these two pointers ever met. If the loop is detected, the start of the loop can help us remove the detected loop in the linked list. It is called Floyd's Cycle-Finding Algorithm. The given diagram shows how a loop looks like in a linked list:

26) What will you prefer for traversing through a list of elements between singly and doubly linked lists?

Double linked lists need more space for each node in comparison to the singly linked list. In a doubly linked list, the elementary operations such as insertion and deletion are more expensive, but they are easier to manipulate because they provide quick and easy sequential access to the list in both the directions. But, doubly linked lists cannot be used as persistent data structures. Hence, the doubly linked list would be a better choice for traversing through a list of the node.

27) Where will be the free node available while inserting a new node in a linked list?

If a new node is inserted in a linked list, the free node is found in Avail List.

28) For which header list, the last node contains the null pointer?

For grounded header list, you will find the last node containing the null pointer.

29) How can you traverse a linked list in Java?

There are several ways to traverse a linked list in Java, e.g., we can use traditional for, while, or do-while loops and go through the linked list until we reach at the end of the linked list. Alternatively, we can use enhanced for loop of Java 1.5 or iterator to traverse through a linked list in Java. From JDK 8 onwards, we have an option to use java.util.stream.Stream for traversing a linked list.

30) How to calculate the length of a singly linked list in Java?

We can iterate over the linked list and keep a count of nodes until we reach the end of the linked list where the next node will be null. The value of the counter is considered as the length of the linked list.

31) How can someone display singly linked list from first to last?

One must follow these steps to display singly linked list from first to last:

• Create a linked list using create().
• The address stored inside the global variable "start" cannot be changed, so one must declare one temporary variable "temp" of type node.
• To traverse from start to end, one should assign the address of starting node in the pointer variable, i.e., temp.

If the temp is NULL, then it means that the last node is accessed.

32) Mention some drawbacks of the linked list.

Some of the important drawbacks of the linked list are given below:

• Random access is not allowed. We need to access elements sequentially starting from the first node. So we cannot perform a binary search with linked lists.
• More memory space for a pointer is required with each element of the list.
• Slow O(n) index access, since accessing linked list by index means we have to loop over the list recursively.
• Poor locality, the memory used for the linked list is scattered around in a mess.

33) Mention a package that is used for Linked List class in Java.

The package that is used for Linked list in Java is java.util.

34) Mention some interfaces implemented by Linked List in Java.

Some of the main interfaces implemented by Java Linked Lists are:

• Serializable
• Queue
• List
• Cloneable
• Collection
• Deque
• Iterable

35) How can we find the sum of two linked lists using Stack in Java?

To calculate the sum of the linked lists, we calculate the sum of values held at nodes in the same position. For example, we add values at first node on both the linked list to find the value of the first node of the resultant linked list. If the length of both linked lists is not equal, then we only add elements from the shorter linked list and copy values for remaining nodes from the long list.

Linked List In C++

We will take a look at the singly linked list in detail in this tutorial.

The following diagram shows the structure of a singly linked list.

As shown above, the first node of the linked list is called “head” while the last node is called “Tail”. As we see, the last node of the linked list will have its next pointer as null since it will not have any memory address pointed to.

Since each node has a pointer to the next node, data items in the linked list need not be stored at contiguous locations. The nodes can be scattered in the memory. We can access the nodes anytime as each node will have an address of the next node.

We can add data items to the linked list as well as delete items from the list easily. Thus it is possible to grow or shrink the linked list dynamically. There is no upper limit on how many data items can be there in the linked list. So as long as memory is available, we can have as many data items added to the linked list.

Apart from easy insertion and deletion, the linked list also doesn’t waste memory space as we need not specify beforehand how many items we need in the linked list. The only space taken by linked list is for storing the pointer to the next node that adds a little overhead.

Next, we will discuss the various operations that can be performed on a linked list.

Operations

Just like the other data structures, we can perform various operations for the linked list as well. But unlike arrays, in which we can access the element using subscript directly even if it is somewhere in between, we cannot do the same random access with a linked list.

In order to access any node, we need to traverse the linked list from the start and only then we can access the desired node. Hence accessing the data randomly from the linked list proves to be expensive.

We can perform various operations on a linked list as given below:

#1) Insertion

Insertion operation of linked list adds an item to the linked list. Though it may sound simple, given the structure of the linked list, we know that whenever a data item is added to the linked list, we need to change the next pointers of the previous and next nodes of the new item that we have inserted.

The second thing that we have to consider is the place where the new data item is to be added.

There are three positions in the linked list where a data item can be added.

#1) At the beginning of the linked list

A linked list is shown below 2->4->6->8->10. If we want to add a new node 1, as the first node of the list, then the head pointing to node 2 will now point to 1 and the next pointer of node 1 will have a memory address of node 2 as shown in the below figure.

Thus the new linked list becomes 1->2->4->6->8->10.

#2) After the given Node

Here, a node is given and we have to add a new node after the given node. In the below-linked list a->b->c->d ->e, if we want to add a node f after node c then the linked list will look as follows:

Thus in the above diagram, we check if the given node is present. If it’s present, we create a new node f. Then we point the next pointer of node c to point to the new node f. The next pointer of the node f now points to node d.

#3) At the end of the Linked List

In the third case, we add a new node at the end of the linked list. Consider we have the same linked list a->b->c->d->e and we need to add a node f to the end of the list. The linked list will look as shown below after adding the node.

Thus we create a new node f. Then the tail pointer pointing to null is pointed to f and the next pointer of node f is pointed to null. We have implemented all three types of insert functions in the below C++ program.

In C++, we can declare a linked list as a structure or as a class. Declaring linked list as a structure is a traditional C-style declaration. A linked list as a class is used in modern C++, mostly while using standard template library.

In the following program, we have used structure to declare and create a linked list. It will have data and pointer to the next element as its members.

Output:

Finallinkedlist:

30–>20–>50–>10–>40–>null

Next, we implement the linked list insert operation in Java. In Java language, the linked list is implemented as a class. The program below is similar in logic to the C++ program, the only difference is that we use a class for the linked list.

Output:

Finallinkedlist:

10–>20–>30–>40–>50–>null

In both the program above, C++ as well as Java, we have separate functions to add a node in front of the list, end of the list and between the lists given in a node. In the end, we print the contents of the list created using all the three methods.

#2) Deletion

Like insertion, deleting a node from a linked list also involves various positions from where the node can be deleted. We can delete the first node, last node or a random kth node from the linked list. After deletion, we need to adjust the next pointer and the other pointers in the linked list appropriately so as to keep the linked list intact.

In the following C++ implementation, we have given two methods of deletion i.e. deleting the first node in the list and deleting the last node in the list. We first create a list by adding nodes to the head. Then we display the contents of the list after insertion and each deletion.

Output:

Linkedlistcreated

10–>8–>6–>4–>2–
>NULL

Linkedlistafterdeletingheadnode

8–>6–>4–>2–
>NULL

Linkedlistafterdeletinglastnode

8–>6–>4–>NULL

Next is the Java implementation for deleting nodes from the linked list. The implementation logic is the same as used in the C++ program. The only difference is that the linked list is declared as a class.

Output:

Linkedlistcreated:

9–>7–>5–>3–>1–
>null

Linkedlistafterdeletingheadnode:

7–>5–>3–>1–
>null

Linkedlistafterdeletinglastnode:

7–>5–>3–>null

Count The Number Of Nodes

The operation to count the number of nodes can be performed while traversing the linked list. We have already seen in the implementation above that whenever we need to insert/delete a node or display contents of the linked list, we need to traverse the linked list from start.

Keeping a counter and incrementing it as we traverse each node will give us the count of the number of nodes present in the linked list. We will leave this program for the readers to implement.

Arrays And Linked Lists

Having seen the operations and implementation of the linked list, let us compare how arrays and linked list fair in comparison with each other.

Applications

As arrays and linked lists are both used to store items and are linear data structures, both these structures can be used in similar ways for most of the applications.

Some of the applications for linked lists are as follows:

• A linked list can be used to implement stacks and queues.
• A linked list can also be used to implement graphs whenever we have to represent graphs as adjacency lists.
• A mathematical polynomial can be stored as a linked list.
• In the case of hashing technique, the buckets used in hashing are implemented using the linked lists.
• Whenever a program requires dynamic allocation of memory, we can use a linked list as linked lists work more efficiently in this case.

Conclusion

Linked lists are the data structures that are used to store data items in a linear fashion but noncontiguous locations. A linked list is a collection of nodes that contain a data part and a next pointer that contains the memory address of the next element in the list.

The last element in the list has its next pointer set to NULL, thereby indicating the end of the list. The first element of the list is called the Head. The linked list supports various operations like insertion, deletion, traversal, etc. In case of dynamic memory allocation, linked lists are preferred over arrays.

Linked lists are expensive as far as their traversal is concerned since we cannot randomly access the elements like arrays. However, insertion-deletion operations are less expensive when compared arrays.

We have learned all about linear linked lists in this tutorial. Linked lists can also be circular or doubly. We will have an in-depth look at these lists in our upcoming tutorials.

=> Check Here For Complete C++ Training Series.