What is singly linked list also write its algorithm for insertion?

Insertion in singly linked list at beginning

Inserting a new element into a singly linked list at beginning is quite simple. We just need to make a few adjustments in the node links. There are the following steps which need to be followed in order to inser a new node in the list at beginning.

Allocate the space for the new node and store data into the data part of the node. This will be done by the following statements.

Make the link part of the new node pointing to the existing first node of the list. This will be done by using the following statement.

At the last, we need to make the new node as the first node of the list this will be done by using the following statement.

Insertion in singly linked list at the end

In order to insert a node at the last, there are two following scenarios which need to be mentioned.

The node is being added to an empty list
The node is being added to the end of the linked list

Insertion Sort for Singly Linked List

We have discussed Insertion Sort for arrays. In this article we are going to discuss Insertion Sort for linked list.
Below is a simple insertion sort algorithm for a linked list.

1) Create an empty sorted (or result) list 2) Traverse the given list, do following for every node. ......a) Insert current node in sorted way in sorted or result list. 3) Change head of given linked list to head of sorted (or result) list.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The main step is (2.a) which has been covered in the below post.
Sorted Insert for Singly Linked List

Below is implementation of above algorithm

// C program to sort link list
// using insertion sort
#include <stdio.h>
#include <stdlib.h>

struct node {

int data;

struct node* next;
};

struct node* head = NULL;

struct node* sorted = NULL;

void push(int val)
{

/* allocate node */

struct node* newnode

= (struct node*)malloc(sizeof(struct node));

newnode->data = val;

/* link the old list off the new node */

newnode->next = head;

/* move the head to point to the new node */

head = newnode;
}
/*

* function to insert a new_node in a list. Note that

* this function expects a pointer to head_ref as this

* can modify the head of the input linked list

* (similar to push())

*/

void sortedInsert(struct node* newnode)
{

/* Special case for the head end */

if (sorted == NULL || sorted->data >= newnode->data) {

newnode->next = sorted;

sorted = newnode;

}

else {

struct node* current = sorted;

/* Locate the node before the point of insertion

*/

while (current->next != NULL

&& current->next->data < newnode->data) {

current = current->next;

}

newnode->next = current->next;

current->next = newnode;

}
}
// function to sort a singly linked list 
// using insertion sort

void insertionsort()
{

struct node* current = head;

// Traverse the given linked list and insert every

// node to sorted

while (current != NULL) {

// Store next for next iteration

struct node* next = current->next;

// insert current in sorted linked list

sortedInsert(current);

// Update current

current = next;

}

// Update head to point to sorted linked list

head = sorted;
}
/* Function to print linked list */

void printlist(struct node* head)
{

while (head != NULL) {

printf("%d->", head->data);

head = head->next;

}

printf("NULL");
}
// Driver program to test above functions

int main()
{

push(5);

push(20);

push(4);

push(3);

push(30);

printf("Linked List before sorting:\n");

printlist(head);

printf("\n");

insertionsort(head);

printf("Linked List after sorting:\n");

printlist(head);
}
// This code is contributed by Sornodeep Chandra

C++

// C++ program to sort link list
// using insertion sort
#include <bits/stdc++.h>

using namespace std;

struct Node {

int val;

struct Node* next;

Node(int x)

{

val = x;

next = NULL;

}
};

class LinkedlistIS {

public:

Node* head;

Node* sorted;

void push(int val)

{

/* allocate node */

Node* newnode = new Node(val);

/* link the old list off the new node */

newnode->next = head;

/* move the head to point to the new node */

head = newnode;

}

// function to sort a singly linked list using insertion

// sort

void insertionSort(Node* headref)

{

// Initialize sorted linked list

sorted = NULL;

Node* current = headref;

// Traverse the given linked list and insert every

// node to sorted

while (current != NULL) {

// Store next for next iteration

Node* next = current->next;

// insert current in sorted linked list

sortedInsert(current);

// Update current

current = next;

}

// Update head_ref to point to sorted linked list

head = sorted;

}

/*

* function to insert a new_node in a list. Note that

* this function expects a pointer to head_ref as this

* can modify the head of the input linked list

* (similar to push())

*/

void sortedInsert(Node* newnode)

{

/* Special case for the head end */

if (sorted == NULL || sorted->val >= newnode->val) {

newnode->next = sorted;

sorted = newnode;

}

else {

Node* current = sorted;

/* Locate the node before the point of insertion

*/

while (current->next != NULL

&& current->next->val < newnode->val) {

current = current->next;

}

newnode->next = current->next;

current->next = newnode;

}

}

/* Function to print linked list */

void printlist(Node* head)

{

while (head != NULL) {

cout << head->val << " ";

head = head->next;

}

}
};
// Driver program to test above functions

int main()
{

LinkedlistIS list;

list.head = NULL;

list.push(5);

list.push(20);

list.push(4);

list.push(3);

list.push(30);

cout << "Linked List before sorting" << endl;

list.printlist(list.head);

cout << endl;

list.insertionSort(list.head);

cout << "Linked List After sorting" << endl;

list.printlist(list.head);
}
// This code is contributed by nirajgusain5

Java

// Java program to sort link list
// using insertion sort

public class LinkedlistIS
{

node head;

node sorted;

class node

{

int val;

node next;

public node(int val)

{

this.val = val;

}

}

void push(int val)

{

/* allocate node */

node newnode = new node(val);

/* link the old list off the new node */

newnode.next = head;

/* move the head to point to the new node */

head = newnode;

}

// function to sort a singly linked list using insertion sort

void insertionSort(node headref)

{

// Initialize sorted linked list

sorted = null;

node current = headref;

// Traverse the given linked list and insert every

// node to sorted

while (current != null)

{

// Store next for next iteration

node next = current.next;

// insert current in sorted linked list

sortedInsert(current);

// Update current

current = next;

}

// Update head_ref to point to sorted linked list

head = sorted;

}

/*

* function to insert a new_node in a list. Note that

* this function expects a pointer to head_ref as this

* can modify the head of the input linked list

* (similar to push())

*/

void sortedInsert(node newnode)

{

/* Special case for the head end */

if (sorted == null || sorted.val >= newnode.val)

{

newnode.next = sorted;

sorted = newnode;

}

else

{

node current = sorted;

/* Locate the node before the point of insertion */

while (current.next != null && current.next.val < newnode.val)

{

current = current.next;

}

newnode.next = current.next;

current.next = newnode;

}

}

/* Function to print linked list */

void printlist(node head)

{

while (head != null)

{

System.out.print(head.val + " ");

head = head.next;

}

}

// Driver program to test above functions

public static void main(String[] args)

{

LinkedlistIS list = new LinkedlistIS();

list.push(5);

list.push(20);

list.push(4);

list.push(3);

list.push(30);

System.out.println("Linked List before Sorting..");

list.printlist(list.head);

list.insertionSort(list.head);

System.out.println("\nLinkedList After sorting");

list.printlist(list.head);

}
}
// This code is contributed by Rishabh Mahrsee

Python

# Python implementation of above algorithm
# Node class 

class Node:

# Constructor to initialize the node object

def __init__(self, data):

self.data = data

self.next = None
# function to sort a singly linked list using insertion sort

def insertionSort(head_ref):

# Initialize sorted linked list

sorted = None

# Traverse the given linked list and insert every

# node to sorted

current = head_ref

while (current != None):

# Store next for next iteration

next = current.next

# insert current in sorted linked list

sorted = sortedInsert(sorted, current)

# Update current

current = next

# Update head_ref to point to sorted linked list

head_ref = sorted

return head_ref
# function to insert a new_node in a list. Note that this
# function expects a pointer to head_ref as this can modify the
# head of the input linked list (similar to push())

def sortedInsert(head_ref, new_node):

current = None

# Special case for the head end */

if (head_ref == None or (head_ref).data >= new_node.data):

new_node.next = head_ref

head_ref = new_node

else:

# Locate the node before the point of insertion

current = head_ref

while (current.next != None and

current.next.data < new_node.data):

current = current.next

new_node.next = current.next

current.next = new_node

return head_ref
# BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert 
# Function to print linked list */

def printList(head):

temp = head

while(temp != None):

print( temp.data, end = " ")

temp = temp.next

# A utility function to insert a node
# at the beginning of linked list 

def push( head_ref, new_data):

# allocate node

new_node = Node(0)

# put in the data

new_node.data = new_data

# link the old list off the new node

new_node.next = (head_ref)

# move the head to point to the new node

(head_ref) = new_node

return head_ref
# Driver program to test above functions

a = None

a = push(a, 5)

a = push(a, 20)

a = push(a, 4)

a = push(a, 3)

a = push(a, 30)

print("Linked List before sorting ")
printList(a)

a = insertionSort(a)

print("\nLinked List after sorting ")
printList(a)
# This code is contributed by Arnab Kundu

// C# program to sort link list
// using insertion sort

using System;

public class LinkedlistIS
{

public node head;

public node sorted;

public class node

{

public int val;

public node next;

public node(int val)

{

this.val = val;

}

}

void push(int val)

{

/* allocate node */

node newnode = new node(val);

/* link the old list off the new node */

newnode.next = head;

/* move the head to point to the new node */

head = newnode;

}

// function to sort a singly

// linked list using insertion sort

void insertionSort(node headref)

{

// Initialize sorted linked list

sorted = null;

node current = headref;

// Traverse the given

// linked list and insert every

// node to sorted

while (current != null)

{

// Store next for next iteration

node next = current.next;

// insert current in sorted linked list

sortedInsert(current);

// Update current

current = next;

}

// Update head_ref to point to sorted linked list

head = sorted;

}

/*

* function to insert a new_node in a list. Note that

* this function expects a pointer to head_ref as this

* can modify the head of the input linked list

* (similar to push())

*/

void sortedInsert(node newnode)

{

/* Special case for the head end */

if (sorted == null || sorted.val >= newnode.val)

{

newnode.next = sorted;

sorted = newnode;

}

else

{

node current = sorted;

/* Locate the node before the point of insertion */

while (current.next != null &&

current.next.val < newnode.val)

{

current = current.next;

}

newnode.next = current.next;

current.next = newnode;

}

}

/* Function to print linked list */

void printlist(node head)

{

while (head != null)

{

Console.Write(head.val + " ");

head = head.next;

}

}

// Driver code

public static void Main(String[] args)

{

LinkedlistIS list = new LinkedlistIS();

list.push(5);

list.push(20);

list.push(4);

list.push(3);

list.push(30);

Console.WriteLine("Linked List before Sorting..");

list.printlist(list.head);

list.insertionSort(list.head);

Console.WriteLine("\nLinkedList After sorting");

list.printlist(list.head);

}
}
// This code contributed by Rajput-Ji

Javascript

<script>
// javascript program to sort link list
// using insertion sort

var head = null;

var sorted = null;

class node {

constructor(val) {

this.val = val;

this.next = null;

}

}

function push(val) {

/* allocate node */

var newnode = new node(val);

/* link the old list off the new node */

newnode.next = head;

/* move the head to point to the new node */

head = newnode;

}

// function to sort a singly linked list using insertion sort

function insertionSort( headref) {

// Initialize sorted linked list

var sorted = null;

var current = headref;

// Traverse the given linked list and insert every

// node to sorted

while (current != null) {

// Store next for next iteration

var next = current.next;

// insert current in sorted linked list

sortedInsert(current);

// Update current

current = next;

}

// Update head_ref to point to sorted linked list

head = sorted;

}

/*

* function to insert a new_node in a Note that this function expects a

* pointer to head_ref as this can modify the head of the input linked list

* (similar to push())

*/

function sortedInsert( newnode) {

/* Special case for the head end */

if (sorted == null || sorted.val >= newnode.val) {

newnode.next = sorted;

sorted = newnode;

} else {

var current = sorted;

/* Locate the node before the point of insertion */

while (current.next != null && current.next.val < newnode.val) {

current = current.next;

}

newnode.next = current.next;

current.next = newnode;

}

}

/* Function to print linked list */

function printlist( head) {

while (head != null) {

document.write(head.val + " ");

head = head.next;

}

}

// Driver program to test above functions

push(5);

push(20);

push(4);

push(3);

push(30);

document.write("Linked List before Sorting..<br/>");

printlist(head);

insertionSort(head);

document.write("<br/>LinkedList After sorting<br/>");

printlist(sorted);
// This code contributed by aashish2995 
</script>

Output:

Linked List before sorting 30 3 4 20 5 Linked List after sorting 3 4 5 20 30

Time and space complexity analysis:

In worst case we might have to traverse all nodes of the sorted list for inserting a node. And there are “n” such nodes.

Thus Time Complexity: O(n)*O(n)=O(n^2)

Space Complexity: No extra space is required depending on the size of the input. Thus Space complexity is constant- O(1).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Article Tags :

Linked List

Practice Tags :

Linked List

Read Full Article

Linked List Operations: Traverse, Insert and Delete

In this tutorial, you will learn different operations on a linked list. Also, you will find implementation of linked list operations in C/C++, Python and Java.

There are various linked list operations that allow us to perform different actions on linked lists. For example, the insertion operation adds a new element to the linked list.

Here's a list of basic linked list operations that we will cover in this article.

Traversal - access each element of the linked list
Insertion - adds a new element to the linked list
Deletion - removes the existing elements
Search - find a node in the linked list
Sort - sort the nodes of the linked list

Before you learn about linked list operations in detail, make sure to know about Linked List first.

Things to Remember about Linked List

head points to the first node of the linked list
next pointer of the last node is NULL, so if the next current node is NULL, we have reached the end of the linked list.

In all of the examples, we will assume that the linked list has three nodes 1 --->2 --->3 with node structure as below:

struct node { int data; struct node *next; };

Data Structure and Algorithms - Linked List

Types of Linked List and Operation on Linked List

In the previous blog, we have seen the structure and properties of a Linked List. In this blog, we will discuss the types of a linked list and basic operations that can be performed on a linked list.

Types of Linked List

Following are the types of linked list

Singly Linked List.
Doubly Linked List.
Circular Linked List.

Singly Linked List

A Singly-linked list is a collection of nodes linked together in a sequential way where each node of the singly linked list contains a data field and an address field that contains the reference of the next node.

The structure of the node in the Singly Linked List is

class Node { int data // variable to store the data of the node Node next // variable to store the address of the next node }

The nodes are connected to each other in this form where the value of the next variable of the last node is NULL i.e. next = NULL, which indicates the end of the linked list.

Doubly Linked List

A Doubly Linked List contains an extra memory to store the address of the previous node, together with the address of the next node and data which are there in the singly linked list. So, here we are storing the address of the next as well as the previous nodes.

The following is the structure of the node in the Doubly Linked List(DLL):

class DLLNode { int val // variable to store the data of the node DLLNode prev // variable to store the address of the previous node DLLNode next // variable to store the address of the next node }

The nodes are connected to each other in this form where the first node has prev = NULL and the last node has next = NULL.

Advantages over Singly Linked List-

It can be traversed both forward and backward direction.
The delete operation is more efficient if the node to be deleted is given. (Think! you will get the answer in the second half of this blog)
The insert operation is more efficient if the node is given before which insertion should take place. (Think!)

Disadvantages over Singly Linked List-

It will require more space as each node has an extra memory to store the address of the previous node.
The number of modification increase while doing various operations like insertion, deletion, etc.

Circular Linked List

A circular linked list is either a singly or doubly linked list in which there are no NULL values. Here, we can implement the Circular Linked List by making the use of Singly or Doubly Linked List. In the case of a singly linked list, the next of the last node contains the address of the first node and in case of a doubly-linked list, the next of last node contains the address of the first node and prev of the first node contains the address of the last node.

Advantages of a Circular linked list

The list can be traversed from any node.
Circular lists are the required data structure when we want a list to be accessed in a circle or loop.
We can easily traverse to its previous node in a circular linked list, which is not possible in a singly linked list. (Think!)

Disadvantages of Circular linked list

If not traversed carefully, then we could end up in an infinite loop because here we don't have any NULL value to stop the traversal.
Operations in a circular linked list are complex as compared to a singly linked list and doubly linked list like reversing a circular linked list, etc.

Basic Operations on Linked List

Traversal: To traverse all the nodes one after another.
Insertion: To add a node at the given position.
Deletion: To delete a node.
Searching: To search an element(s) by value.
Updating: To update a node.
Sorting: To arrange nodes in a linked list in a specific order.
Merging: To merge two linked lists into one.

We will see the various implementation of these operations on a singly linked list.

Following is the structure of the node in a linked list:

class Node{ int data // variable containing the data of the node Node next // variable containing the address of next node }

Linked List Traversal

The idea here is to step through the list from beginning to end. For example, we may want to print the list or search for a specific node in the list.

The algorithm for traversing a list

Start with the head of the list. Access the content of the head node if it is not null.
Then go to the next node(if exists) and access the node information
Continue until no more nodes (that is, you have reached the null node)

void traverseLL(Node head) { while(head != NULL) { print(head.data) head = head.next } }

Linked List node Insertion

There can be three cases that will occur when we are inserting a node in a linked list.

Insertion at the beginning
Insertion at the end. (Append)
Insertion after a given node

Insertion at the beginning

Since there is no need to find the end of the list. If the list is empty, we make the new node as the head of the list. Otherwise, we we have to connect the new node to the current head of the list and make the new node, the head of the list.

// function is returning the head of the singly linked-list Node insertAtBegin(Node head, int val) { newNode = new Node(val) // creating new node of linked list if(head == NULL) // check if linked list is empty return newNode else // inserting the node at the beginning { newNode.next = head return newNode } }

Insertion at end

We will traverse the list until we find the last node. Then we insert the new node to the end of the list. Note that we have to consider special cases such as list being empty.

In case of a list being empty, we will return the updated head of the linked list because in this case, the inserted node is the first as well as the last node of the linked list.

// the function is returning the head of the singly linked list Node insertAtEnd(Node head, int val) { if( head == NULL ) // handing the special case { newNode = new Node(val) head = newNode return head } Node temp = head // traversing the list to get the last node while( temp.next != NULL ) { temp = temp.next } newNode = new Node(val) temp.next = newNode return head }

Insertion after a given node

We are given the reference to a node, and the new node is inserted after the given node.

void insertAfter(Node prevNode, int val) { newNode = new Node(val) newNode.next = prevNode.next prevNode.next = newNode }

NOTE: If the address of the prevNode is not given, then you can traverse to that node by finding the data value.

Linked List node Deletion

To delete a node from a linked list, we need to do these steps

Find the previous node of the node to be deleted.
Change the next pointer of the previous node
Free the memory of the deleted node.

In the deletion, there is a special case in which the first node is deleted. In this, we need to update the head of the linked list.

// this function will return the head of the linked list Node deleteLL(Node head, Node del) { if(head == del) // if the node to be deleted is the head node { return head.next // special case for the first Node } Node temp = head while( temp.next != NULL ) { if(temp.next == del) // finding the node to be deleted { temp.next = temp.next.next delete del // free the memory of that Node return head } temp = temp.next } return head // if no node matches in the Linked List }

Linked List node Searching

To search any value in the linked list, we can traverse the linked list and compares the value present in the node.

bool searchLL(Node head, int val) { Node temp = head // creating a temp variable pointing to the head of the linked list while( temp != NULL) // traversing the list { if( temp.data == val ) return true temp = temp.next } return false }

Linked List node Updation

To update the value of the node, we just need to set the data part to the new value.

Below is the implementation in which we had to update the value of the first node in which data is equal to val and we have to set it to newVal.

void updateLL(Node head, int val, int newVal) { Node temp = head while(temp != NULL) { if( temp.data == val) { temp.data = newVal return } temp = temp.next } }

Basic concepts and nomenclatureEdit

Each record of a linked list is often called an 'element' or 'node'.

The field of each node that contains the address of the next node is usually called the 'next link' or 'next pointer'. The remaining fields are known as the 'data', 'information', 'value', 'cargo', or 'payload' fields.

The 'head' of a list is its first node. The 'tail' of a list may refer either to the rest of the list after the head, or to the last node in the list. In Lisp and some derived languages, the next node may be called the 'cdr' (pronounced could-er) of the list, while the payload of the head node may be called the 'car'.

Singly linked listEdit

Singly linked lists contain nodes which have a data field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.

A singly linked list whose nodes contain two fields: an integer value and a link to the next node

The following code demonstrates how to add a new node with data "value" to the end of a singly linked list:

node addNode(node head, int value) { node temp, p; // declare two nodes temp and p temp = createNode(); // assume createNode creates a new node with data = 0 and next pointing to NULL. temp->data = value; // add element's value to data part of node if (head == NULL) { head = temp; // when linked list is empty } else { p = head; // assign head to p while (p->next != NULL) { p = p->next; // traverse the list until p is the last node. The last node always points to NULL. } p->next = temp; // Point the previous last node to the new node created. } return head; }

Doubly linked listEdit

In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').

A doubly linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node

A technique known as XOR-linking allows a doubly linked list to be implemented using a single link field in each node. However, this technique requires the ability to do bit operations on addresses, and therefore may not be available in some high-level languages.

Many modern operating systems use doubly linked lists to maintain references to active processes, threads, and other dynamic objects.[2] A common strategy for rootkits to evade detection is to unlink themselves from these lists.[3]

Multiply linked listEdit

In a 'multiply linked list', each node contains two or more link fields, each field being used to connect the same set of data records in a different order of same set (e.g., by name, by department, by date of birth, etc.). While doubly linked lists can be seen as special cases of multiply linked list, the fact that the two and more orders are opposite to each other leads to simpler and more efficient algorithms, so they are usually treated as a separate case.

Circular linked listEdit

In the last node of a list, the link field often contains a null reference, a special value is used to indicate the lack of further nodes. A less common convention is to make it point to the first node of the list; in that case, the list is said to be 'circular' or 'circularly linked'; otherwise, it is said to be 'open' or 'linear'. It is a list where the last pointer points to the first node.

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

Sentinel nodesEdit

In some implementations an extra 'sentinel' or 'dummy' node may be added before the first data record or after the last one. This convention simplifies and accelerates some list-handling algorithms, by ensuring that all links can be safely dereferenced and that every list (even one that contains no data elements) always has a "first" and "last" node.

Empty listsEdit

An empty list is a list that contains no data records. This is usually the same as saying that it has zero nodes. If sentinel nodes are being used, the list is usually said to be empty when it has only sentinel nodes.

Hash linkingEdit

The link fields need not be physically part of the nodes. If the data records are stored in an array and referenced by their indices, the link field may be stored in a separate array with the same indices as the data records.

List handlesEdit

Since a reference to the first node gives access to the whole list, that reference is often called the 'address', 'pointer', or 'handle' of the list. Algorithms that manipulate linked lists usually get such handles to the input lists and return the handles to the resulting lists. In fact, in the context of such algorithms, the word "list" often means "list handle". In some situations, however, it may be convenient to refer to a list by a handle that consists of two links, pointing to its first and last nodes.

Combining alternativesEdit

The alternatives listed above may be arbitrarily combined in almost every way, so one may have circular doubly linked lists without sentinels, circular singly linked lists with sentinels, etc.

TradeoffsEdit

As with most choices in computer programming and design, no method is well suited to all circumstances. A linked list data structure might work well in one case, but cause problems in another. This is a list of some of the common tradeoffs involving linked list structures.

Linked lists vs. dynamic arraysEdit

A dynamic array is a data structure that allocates all elements contiguously in memory, and keeps a count of the current number of elements. If the space reserved for the dynamic array is exceeded, it is reallocated and (possibly) copied, which is an expensive operation.

Linked lists have several advantages over dynamic arrays. Insertion or deletion of an element at a specific point of a list, assuming that we have indexed a pointer to the node (before the one to be removed, or before the insertion point) already, is a constant-time operation (otherwise without this reference it is O(n)), whereas insertion in a dynamic array at random locations will require moving half of the elements on average, and all the elements in the worst case. While one can "delete" an element from an array in constant time by somehow marking its slot as "vacant", this causes fragmentation that impedes the performance of iteration.

Moreover, arbitrarily many elements may be inserted into a linked list, limited only by the total memory available; while a dynamic array will eventually fill up its underlying array data structure and will have to reallocate—an expensive operation, one that may not even be possible if memory is fragmented, although the cost of reallocation can be averaged over insertions, and the cost of an insertion due to reallocation would still be amortized O(1). This helps with appending elements at the array's end, but inserting into (or removing from) middle positions still carries prohibitive costs due to data moving to maintain contiguity. An array from which many elements are removed may also have to be resized in order to avoid wasting too much space.

On the other hand, dynamic arrays (as well as fixed-size array data structures) allow constant-time random access, while linked lists allow only sequential access to elements. Singly linked lists, in fact, can be easily traversed in only one direction. This makes linked lists unsuitable for applications where it's useful to look up an element by its index quickly, such as heapsort. Sequential access on arrays and dynamic arrays is also faster than on linked lists on many machines, because they have optimal locality of reference and thus make good use of data caching.

Another disadvantage of linked lists is the extra storage needed for references, which often makes them impractical for lists of small data items such as characters or boolean values, because the storage overhead for the links may exceed by a factor of two or more the size of the data. In contrast, a dynamic array requires only the space for the data itself (and a very small amount of control data).[note 1] It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element, a problem generally solved using memory pools.

Some hybrid solutions try to combine the advantages of the two representations. Unrolled linked lists store several elements in each list node, increasing cache performance while decreasing memory overhead for references. CDR coding does both these as well, by replacing references with the actual data referenced, which extends off the end of the referencing record.

A good example that highlights the pros and cons of using dynamic arrays vs. linked lists is by implementing a program that resolves the Josephus problem. The Josephus problem is an election method that works by having a group of people stand in a circle. Starting at a predetermined person, one may count around the circle n times. Once the nth person is reached, one should remove them from the circle and have the members close the circle. The process is repeated until only one person is left. That person wins the election. This shows the strengths and weaknesses of a linked list vs. a dynamic array, because if the people are viewed as connected nodes in a circular linked list, then it shows how easily the linked list is able to delete nodes (as it only has to rearrange the links to the different nodes). However, the linked list will be poor at finding the next person to remove and will need to search through the list until it finds that person. A dynamic array, on the other hand, will be poor at deleting nodes (or elements) as it cannot remove one node without individually shifting all the elements up the list by one. However, it is exceptionally easy to find the nth person in the circle by directly referencing them by their position in the array.

The list ranking problem concerns the efficient conversion of a linked list representation into an array. Although trivial for a conventional computer, solving this problem by a parallel algorithm is complicated and has been the subject of much research.

A balanced tree has similar memory access patterns and space overhead to a linked list while permitting much more efficient indexing, taking O(log n) time instead of O(n) for a random access. However, insertion and deletion operations are more expensive due to the overhead of tree manipulations to maintain balance. Schemes exist for trees to automatically maintain themselves in a balanced state: AVL trees or red–black trees.

Singly linked linear lists vs. other listsEdit

While doubly linked and circular lists have advantages over singly linked linear lists, linear lists offer some advantages that make them preferable in some situations.

A singly linked linear list is a recursive data structure, because it contains a pointer to a smaller object of the same type. For that reason, many operations on singly linked linear lists (such as merging two lists, or enumerating the elements in reverse order) often have very simple recursive algorithms, much simpler than any solution using iterative commands. While those recursive solutions can be adapted for doubly linked and circularly linked lists, the procedures generally need extra arguments and more complicated base cases.

Linear singly linked lists also allow tail-sharing, the use of a common final portion of sub-list as the terminal portion of two different lists. In particular, if a new node is added at the beginning of a list, the former list remains available as the tail of the new one—a simple example of a persistent data structure. Again, this is not true with the other variants: a node may never belong to two different circular or doubly linked lists.

In particular, end-sentinel nodes can be shared among singly linked non-circular lists. The same end-sentinel node may be used for every such list. In Lisp, for example, every proper list ends with a link to a special node, denoted by nil or (), whose CAR and CDR links point to itself. Thus a Lisp procedure can safely take the CAR or CDR of any list.

The advantages of the fancy variants are often limited to the complexity of the algorithms, not in their efficiency. A circular list, in particular, can usually be emulated by a linear list together with two variables that point to the first and last nodes, at no extra cost.

Doubly linked vs. singly linkedEdit

Double-linked lists require more space per node (unless one uses XOR-linking), and their elementary operations are more expensive; but they are often easier to manipulate because they allow fast and easy sequential access to the list in both directions. In a doubly linked list, one can insert or delete a node in a constant number of operations given only that node's address. To do the same in a singly linked list, one must have the address of the pointer to that node, which is either the handle for the whole list (in case of the first node) or the link field in the previous node. Some algorithms require access in both directions. On the other hand, doubly linked lists do not allow tail-sharing and cannot be used as persistent data structures.

Circularly linked vs. linearly linkedEdit

A circularly linked list may be a natural option to represent arrays that are naturally circular, e.g. the corners of a polygon, a pool of buffers that are used and released in FIFO ("first in, first out") order, or a set of processes that should be time-shared in round-robin order. In these applications, a pointer to any node serves as a handle to the whole list.

With a circular list, a pointer to the last node gives easy access also to the first node, by following one link. Thus, in applications that require access to both ends of the list (e.g., in the implementation of a queue), a circular structure allows one to handle the structure by a single pointer, instead of two.

A circular list can be split into two circular lists, in constant time, by giving the addresses of the last node of each piece. The operation consists in swapping the contents of the link fields of those two nodes. Applying the same operation to any two nodes in two distinct lists joins the two list into one. This property greatly simplifies some algorithms and data structures, such as the quad-edge and face-edge.

The simplest representation for an empty circular list (when such a thing makes sense) is a null pointer, indicating that the list has no nodes. Without this choice, many algorithms have to test for this special case, and handle it separately. By contrast, the use of null to denote an empty linear list is more natural and often creates fewer special cases.

For some applications, it can be useful to use singly linked lists that can vary between being circular and being linear, or even circular with a linear initial segment. Algorithms for searching or otherwise operating on these have to take precautions to avoid accidentally entering an endless loop. One usual method is to have a second pointer walking the list at half or double the speed, and if both pointers meet at the same node, you know you found a cycle.

Using sentinel nodesEdit

Sentinel node may simplify certain list operations, by ensuring that the next or previous nodes exist for every element, and that even empty lists have at least one node. One may also use a sentinel node at the end of the list, with an appropriate data field, to eliminate some end-of-list tests. For example, when scanning the list looking for a node with a given value x, setting the sentinel's data field to x makes it unnecessary to test for end-of-list inside the loop. Another example is the merging two sorted lists: if their sentinels have data fields set to +∞, the choice of the next output node does not need special handling for empty lists.

However, sentinel nodes use up extra space (especially in applications that use many short lists), and they may complicate other operations (such as the creation of a new empty list).

However, if the circular list is used merely to simulate a linear list, one may avoid some of this complexity by adding a single sentinel node to every list, between the last and the first data nodes. With this convention, an empty list consists of the sentinel node alone, pointing to itself via the next-node link. The list handle should then be a pointer to the last data node, before the sentinel, if the list is not empty; or to the sentinel itself, if the list is empty.

The same trick can be used to simplify the handling of a doubly linked linear list, by turning it into a circular doubly linked list with a single sentinel node. However, in this case, the handle should be a single pointer to the dummy node itself.[8]