Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 15 minutes | Coding time: 20 minutes
In this session, we will explore how to insert an element in a sorted Linked List such that the modified Linked List is sorted as well.
Pseudocode
Let input linked list is sorted in increasing order.
STEP 1) If Linked list is empty then make the node as head and return it.
STEP 2) If value of the node to be inserted is smaller than value of head node, then insert the node at start and make it head.
STEP 3) Find the appropriate node after which the input node is to be inserted. To find the appropriate node start from head, keep moving until we reach a node whose value is greater than the input node. The node just before the node is the appropriate node.
STEP 4) Insert the node after the appropriate node found in step 3.
void sortedInsert(E e)
{
Node current = first;
/* Special case for head node */
if (current == null || current.data >= e)
{
LinkFirst(e);
}
else
{
while (current.next != null && current.next.data < new_node.data)
current = current.next;
final Node<E> newNode = new Node<>(current, e, current.next);
}
}
Implementations
- Java
Java
import java.util.*;
class LinkedList<E> implements java.io.Serializable
{
private static class Node<E>
{
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next)
{
this.item = element;
this.prev = prev;
this.next = next;
}
}
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
// Creates an empty list
public LinkedList() {}
// Sorted Insert in a Linked List
void sortedInsert(E e)
{
Node current = first;
/* Special case for head node */
if (current == null || current.data >= e)
{
LinkFirst(e);
}
else
{
while (current.next != null && current.next.data < new_node.data)
current = current.next;
final Node<E> newNode = new Node<>(current, e, current.next);
}
}
// Return Node at index "index" O(N) time
public Node<E> node( int index)
{
if(index < (size >> 1))
{
Node<E> x = first;
for(int i=0;i<index; ++i)
x = x.next;
return x;
}
else
{
Node<E> x = last;
for(int i=size-1; i>index; --i)
x = x.prev;
return x;
}
}
// Print all elements in the LinkedList
public void printList()
{
Node<E> x = first;
for(int i=0;i<size; ++i)
{
System.out.println(x.item);
x = x.next;
}
}
private void LinkFirst(E e)
{
final Node<E> front = first;
final Node<E> newNode = new Node<>(null, e, front);
first = newNode;
if( front == null)
last = newNode;
else
front.prev = newNode;
++ size;
}
private void LinkLast(E e)
{
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if(l == null)
first = newNode;
else
l.next = newNode;
++ size;
}
// Inserts a node before a non null node succ
private void LinkBefore(E e, Node<E> succ)
{
Node<E> before = succ.prev;
Node<E> newNode = new Node<E>(before, e, succ);
succ.prev = newNode;
if(before == null)
{
first = newNode;
}
else
{
before.next = newNode;
}
++ size;
}
E unlinkFirst(Node<E> f)
{
final Node<E> next = f.next;
first = next;
final E element = f.item;
f.item = null;
f.next = null;
if(next == null)
last = null;
else
next.prev = null;
-- size;
return element;
}
E unlinkLast(Node<E> l)
{
final E element = l.item;
final Node<E> newLast = l.prev;
l.prev = null;
l.item = null;
last = newLast;
if(newLast == null)
first = null;
else
newLast.next = null;
-- size;
return element;
}
E unlink(Node<E> n)
{
final E element = n.item;
final Node<E> before = n.prev;
final Node<E> next = n.next;
if( before == null )
return unlinkFirst(n);
else if(next == null)
return unlinkLast(n);
else
{
n.item = null;
n.next = null;
n.prev = null;
before.next = next;
next.prev = before;
-- size;
}
return element;
}
void add(E e)
{
LinkLast(e);
}
void addAtEnd(E e)
{
LinkLast(e);
}
void addAtFront(E e)
{
LinkFirst(e);
}
}
public class Test_LinkedList
{
public static void main()
{
LinkedList<Integer> ll = new LinkedList<Integer>();
ll.add(10);
ll.add(9);
ll.add(10);
ll.add(100);
Node<Integer> nn = ll.node(3);
ll.unlink(nn);
ll.add(11);
ll.printList();
}
}
Complexity
- Worst case time complexity:
Θ(N) - Average case time complexity:
Θ(N) - Best case time complexity:
Θ(1) - Space complexity:
Θ(1)
Can binary search be used to improve performance?
Yes, binary search can be used in this case but the performance will be the same.
The problem is that random access is not possible in a Linked List. Hence, accessing the middle element in a Linked List takes liner time. Therefore, the binary search takes O(N) time complexity instead of O(log N) in case of an array.
As binary search has no performance advantage compared to linear search in case of a Linked List, linear search is preferred due to simple implementation and single traversal of the Linked List.
