Sorted insertion in doubly linked list

Sorted insertion in doubly linked list

Here given code implementation process.

//C Program
//Sorted insertion in doubly linked list
#include <stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node
{
  int data;
  struct Node*next;
  struct Node*prev;
};
//head and tail pointers
struct Node *head = NULL, *tail = NULL;

//insert Node element of end of linked list
void insert(int value)
{

  //Create a dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL)
  {
    printf("Memory overflow\n");
  }else
  {
    //set data value
    node->data=value;
    node->next=NULL;
    node->prev=NULL;
    if(head==NULL)
    {
      //first node of linked list
      head=node;
      tail=node;

    }
    else if( head->data >= value)
    {
      //Add node at front of linked list
      node->next = head;

      head->prev = node;
      head = node;
    }
    else if(tail->data<=value)
    {
      tail->next = node;
      node->prev = tail;

      tail = node;
    }
    else
    {
        struct Node*temp=head;
        //find last node
        while(temp!=NULL && temp->next!=NULL && temp->next->data < value)
        {
          temp=temp->next;
        }
        //add new node to last positions
        node->next = temp->next;
        if(temp->next!=NULL)
        {
          temp->next->prev=node;
        }
        node->prev = temp;
        temp->next = node;
    }
  }
}
//display element of Nodes
void display() {
  struct Node *temp = head;
  if (temp == NULL) {
    printf("Empty linked list");
  } else {

    printf("\n Head to Tail Nodes : \n");
    //Traverse doubly linked list from front to rear
    while (temp != NULL) {
      //print Node value
      printf("%3d", temp->data);
      temp = temp->next;
    }

    printf("\n Tail to Head Nodes : \n");

    temp = tail;

    //Traverse doubly linked list from rear to front
    while (temp != NULL) {
      //print Node value
      printf("%3d", temp->data);
      temp = temp->prev;
    }
  }

}
int main(){
  
 
  //Insert element of linked list
  insert(3);
  insert(5);
  insert(7);
  insert(12);
  insert(10);
  insert(6);
  insert(4);
  insert(1);
  insert(-1);
  //Display all   
  display();
  return 0;
}

Output

 Head to Tail Nodes : 
 -1  1  3  4  5  6  7 10 12
 Tail to Head Nodes : 
 12 10  7  6  5  4  3  1 -1
/*
 C++ Program
Sorted insertion in doubly linked list
*/

#include<iostream>

using namespace std;
class Node {
  public:
  int data;
  Node *next;
  Node *prev;
  Node(int value) {
    this->data = value;
    this->next = NULL;
    this->prev = NULL;
  }
};
class LinkedList {
public:
  Node *head;
  Node *tail;
  LinkedList() {
    this->head = NULL;
    this->tail = NULL;
  }
  void insert(int value) {
    Node *node = new Node(value);
    if (node == NULL) {
      cout << "Memory overflow\n";
    } else {
      if (this->head == NULL) {
        this->head = node;
        this->tail = node;
      } else
      if (this->head->data >= value) {
        node->next = this->head;
        this->head->prev = node;
        this->head = node;
      } else
      if (this->tail->data <= value) {
        this->tail->next = node;
        this->tail = node;
      } else {
        Node *temp = this->head;
        while (temp != NULL && temp->next != NULL && temp->next->data < value) {
          temp = temp->next;
        }
        node->next = temp->next;
        if (temp->next != NULL) {
          temp->next->prev = node;
        }
        node->prev = temp;
        temp->next = node;
      }
    }
  }
  void display() {
    Node *temp = this->head;
    if (temp == NULL) {
      cout << "\nEmpty linked list\n";
      return;
    }
    cout << "\n Head to Tail Nodes : \n";
    while (temp != NULL) {
      cout << temp->data << "  ";
      temp = temp->next;
    }
    temp = this->tail;
    cout << "\n Tail to Head Nodes : \n";
    while (temp != NULL) {
      cout << temp->data << "  ";
      temp = temp->prev;
    }
  }

};
int main() {
  LinkedList obj;
  obj.insert(3);
  obj.insert(5);
  obj.insert(7);
  obj.insert(12);
  obj.insert(10);
  obj.insert(6);
  obj.insert(4);
  obj.insert(1);
  obj.insert(-1);
  obj.display();
  return 0;
}

Output

 Head to Tail Nodes : 
-1  1  3  4  5  6  7  10  12  
 Tail to Head Nodes : 
12  10  7  6  5  4  3  1  -1 
/*
  Java Program
  Sorted insertion in doubly linked list

*/
class Node {

  public int data;

  public Node next;

  public Node prev;
  
  public Node(int value) {
    //Setup initial values of linked list node
    this.data = value;
    this.next = null;
    this.prev = null;
  }
}
class LinkedList {
  
  public Node head;
  public Node tail;

  public LinkedList()
  {
    head = null;
    tail = null;
  }
  //sorted insert linked list element
  public void insert(int value) {

    Node node = new Node(value);

    if (node == null) {
      System.out.print("Memory overflow\n");
    } 
    else {
   

      if (head == null) {
        //base case empty linked list
        head = node;
        tail = node;
      } 
      else if (head.data >= value) {
        //Add node at begining
        node.next = head;
        head.prev = node;
        head = node;
      }
      else if(tail.data <= value)
      {
        //add node at end 
        tail.next = node;
        tail = node;
      }
       else {
        Node temp = head;

        while (temp != null && temp.next != null && temp.next.data < value) {
          temp = temp.next;
        }
        node.next = temp.next;

        if (temp.next != null) {
          temp.next.prev = node;
        }
       
        node.prev = temp;
        temp.next = node;

      }
    }
  }
  public void display() {
    Node temp = head;
    if (temp == null) {
      System.out.print("\nEmpty linked list\n");
      return;
    } 
    
    System.out.print("\n Head to Tail Nodes : \n");
    
    while (temp != null) {
      System.out.print(temp.data+"  ");
      temp = temp.next;
    }

    temp = tail;

    System.out.print("\n Tail to Head Nodes : \n");
    
    while (temp != null) {
      System.out.print(temp.data+"  ");
      temp = temp.prev;
    }
    
  }
  public static void main(String[] args) {
    LinkedList obj = new LinkedList();
     obj.insert(3);
     obj.insert(5);
     obj.insert(7);
     obj.insert(12);
     obj.insert(10);
     obj.insert( 6);
     obj.insert(4);
     obj.insert(1);
     obj.insert(-1);
     obj.display();
    
  }


}

Output

 Head to Tail Nodes : 
-1  1  3  4  5  6  7  10  12  
 Tail to Head Nodes : 
12  10  7  6  5  4  3  1  -1 
/*
  C# Program
  Sorted insertion in doubly linked list

*/

using System;
public class Node {

	public int data;

	public Node next;

	public Node prev;

	public Node(int value) {
		//Setup initial values of linked list node
		this.data = value;
		this.next = null;
		this.prev = null;
	}
}
class LinkedList {

	public Node head;
	public Node tail;

	public LinkedList()
	{
		head = null;
		tail = null;
	}
	//sorted insert linked list element
	public void insert(int value) {

		Node node = new Node(value);

		if (node == null) {
			Console.Write("Memory overflow\n");
		} 
		else {


			if (head == null) {
				//base case empty linked list
				head = node;
				tail = node;
			} 
			else if (head.data >= value) {
				//Add node at begining
				node.next = head;
				head.prev = node;
				head = node;
			}
			else if(tail.data <= value)
			{
				//add node at end 
				tail.next = node;
				tail = node;
			}
			else {
				Node temp = head;

				while (temp != null && temp.next != null && temp.next.data < value) {
					temp = temp.next;
				}
				node.next = temp.next;

				if (temp.next != null) {
					temp.next.prev = node;
				}

				node.prev = temp;
				temp.next = node;

			}
		}
	}
	public void display() {
		Node temp = head;
		if (temp == null) {
			Console.Write("\nEmpty linked list\n");
			return;
		} 

		Console.Write("\n Head to Tail Nodes : \n");

		while (temp != null) {
			Console.Write(temp.data+"  ");
			temp = temp.next;
		}

		temp = tail;

		Console.Write("\n Tail to Head Nodes : \n");

		while (temp != null) {
			Console.Write(temp.data+"  ");
			temp = temp.prev;
		}

	}
	public static void Main(String[] args) {
		LinkedList obj = new LinkedList();
		obj.insert(3);
		obj.insert(5);
		obj.insert(7);
		obj.insert(12);
		obj.insert(10);
		obj.insert( 6);
		obj.insert(4);
		obj.insert(1);
		obj.insert(-1);
		obj.display();

	}


}

Output

 Head to Tail Nodes : 
-1  1  3  4  5  6  7  10  12  
 Tail to Head Nodes : 
12  10  7  6  5  4  3  1  -1 
# Python 3 Program
# Sorted insertion in doubly linked list

class Node :

  def __init__(self, value) :
    self.data = value
    self.next = None
    self.prev = None
  

class LinkedList :

  def __init__(self) :
    self.head = None
    self.tail = None
  
  def insert(self, value) :
    node = Node(value)
    if (node == None) :
      print("Memory overflow\n")
    else :
      if (self.head == None) :
        self.head = node
        self.tail = node
      elif (self.head.data >= value) :
        node.next = self.head
        self.head.prev = node
        self.head = node
      elif (self.tail.data <= value) :
        self.tail.next = node
        self.tail = node
      else :
        temp = self.head
        while (temp != None and temp.next != None and temp.next.data < value) :
          temp = temp.next
        
        node.next = temp.next
        if (temp.next != None) :
          temp.next.prev = node
        
        node.prev = temp
        temp.next = node
      
    
  
  def display(self) :
    temp = self.head
    if (temp == None) :
      print("\nEmpty linked list\n")
      return
    
    print("\n Head to Tail Nodes : ")
    while (temp != None) :
      print(temp.data ,end="  ")
      temp = temp.next
    
    temp = self.tail
    print("\n Tail to Head Nodes : ")
    while (temp != None) :
      print(temp.data ,end="  ")
      temp = temp.prev
    
  
def main() :
  obj = LinkedList()
  obj.insert(3)
  obj.insert(5)
  obj.insert(7)
  obj.insert(12)
  obj.insert(10)
  obj.insert(6)
  obj.insert(4)
  obj.insert(1)
  obj.insert(-1)
  obj.display()
  

if __name__ == "__main__":
  main()

Output

 Head to Tail Nodes : 
-1  1  3  4  5  6  7  10  12  
 Tail to Head Nodes : 
12  10  7  6  5  4  3  1  -1 
# Ruby Program
#  Sorted insertion in doubly linked list

class Node 
	attr_reader :data, :next, :prev
	attr_accessor :data, :next, :prev
	def initialize(value) 
		self.data = value
		self.next = nil
		self.prev = nil
	end
end

class LinkedList 
	attr_reader :head, :tail
	attr_accessor :head, :tail

	def initialize() 
		@head = nil
		@tail = nil
	end
	def insert(value) 
		node = Node.new(value)
		if (node == nil) 
			print("Memory overflow\n")
		else 
			if (@head == nil) 
				@head = node
				@tail = node
			elsif (@head.data >= value) 
				node.next = @head
				@head.prev = node
				@head = node
			elsif (@tail.data <= value) 
				@tail.next = node
				@tail = node
			else 
				temp = @head
				while (temp != nil and temp.next != nil and temp.next.data < value) 
					temp = temp.next
				end
				node.next = temp.next
				if (temp.next != nil) 
					temp.next.prev = node
				end
				node.prev = temp
				temp.next = node
			end
		end
	end
	def display() 
		temp = @head
		if (temp == nil) 
			print("\nEmpty linked list\n")
			return
		end
		print("\n Head to Tail Nodes  :\n")
		while (temp != nil) 
			print(temp.data ,"  ")
			temp = temp.next
		end
		temp = @tail
		print("\n Tail to Head Nodes  :\n")
		while (temp != nil) 
			print(temp.data ,"  ")
			temp = temp.prev
		end
	end
end

def main() 
	obj = LinkedList.new()
	obj.insert(3)
	obj.insert(5)
	obj.insert(7)
	obj.insert(12)
	obj.insert(10)
	obj.insert(6)
	obj.insert(4)
	obj.insert(1)
	obj.insert(-1)
	obj.display()
end

main()

Output

 Head to Tail Nodes : 
-1  1  3  4  5  6  7  10  12  
 Tail to Head Nodes : 
12  10  7  6  5  4  3  1  -1 
<?php
/*
 Php Program
 Sorted insertion in doubly linked list
*/

class Node {
  public $data;
  public $next;
  public $prev;

  function __construct($value) {
    $this->data = $value;
    $this->next = null;
    $this->prev = null;
  }
}
class LinkedList {
  public $head;
  public $tail;

  function __construct() {
    $this->head = null;
    $this->tail = null;
  }
  public  function insert($value) {
    $node = new Node($value);
    if ($node == null) {
      echo("Memory overflow\n");
    } else {
      if ($this->head == null) {
        $this->head = $node;
        $this->tail = $node;
      } else
      if ($this->head->data >= $value) {
        $node->next = $this->head;
        $this->head->prev = $node;
        $this->head = $node;
      } else
      if ($this->tail->data <= $value) {
        $this->tail->next = $node;
        $this->tail = $node;
      } else {
        $temp = $this->head;
        while ($temp != null && $temp->next != null && $temp->next->data < $value) {
          $temp = $temp->next;
        }
        $node->next = $temp->next;
        if ($temp->next != null) {
          $temp->next->prev = $node;
        }
        $node->prev = $temp;
        $temp->next = $node;
      }
    }
  }
  public  function display() {
    $temp = $this->head;
    if ($temp == null) {
      echo("\nEmpty linked list\n");
      return;
    }
    echo("\n Head to Tail Nodes : \n");
    while ($temp != null) {
      echo($temp->data ."  ");
      $temp = $temp->next;
    }
    $temp = $this->tail;
    echo("\n Tail to Head Nodes : \n");
    while ($temp != null) {
      echo($temp->data ."  ");
      $temp = $temp->prev;
    }
  }

}
function main() {
  $obj = new LinkedList();
  $obj->insert(3);
  $obj->insert(5);
  $obj->insert(7);
  $obj->insert(12);
  $obj->insert(10);
  $obj->insert(6);
  $obj->insert(4);
  $obj->insert(1);
  $obj->insert(-1);
  $obj->display();
}
main();

Output

 Head to Tail Nodes : 
-1  1  3  4  5  6  7  10  12  
 Tail to Head Nodes : 
12  10  7  6  5  4  3  1  -1 
/*
 Node Js Program
 Sorted insertion in doubly linked list
*/

class Node {
	
	constructor(value) {
		this.data = value;
		this.next = null;
		this.prev = null;
	}
}
class LinkedList {
	
	constructor() {
		this.head = null;
		this.tail = null;
	}
	insert(value) {
		var node = new Node(value);
		if (node == null) {
			process.stdout.write("Memory overflow\n");
		} else {
			if (this.head == null) {
				this.head = node;
				this.tail = node;
			} else
			if (this.head.data >= value) {
				node.next = this.head;
				this.head.prev = node;
				this.head = node;
			} else
			if (this.tail.data <= value) {
				this.tail.next = node;
				this.tail = node;
			} else {
				var temp = this.head;
				while (temp != null && temp.next != null && temp.next.data < value) {
					temp = temp.next;
				}
				node.next = temp.next;
				if (temp.next != null) {
					temp.next.prev = node;
				}
				node.prev = temp;
				temp.next = node;
			}
		}
	}
	display() {
		var temp = this.head;
		if (temp == null) {
			process.stdout.write("\nEmpty linked list\n");
			return;
		}
		process.stdout.write("\n Head to Tail Nodes : \n");
		while (temp != null) {
			process.stdout.write(temp.data + "  ");
			temp = temp.next;
		}
		temp = this.tail;
		process.stdout.write("\n Tail to Head Nodes : \n");
		while (temp != null) {
			process.stdout.write(temp.data + "  ");
			temp = temp.prev;
		}
	}
}

function main() {
	var obj = new LinkedList();
	obj.insert(3);
	obj.insert(5);
	obj.insert(7);
	obj.insert(12);
	obj.insert(10);
	obj.insert(6);
	obj.insert(4);
	obj.insert(1);
	obj.insert(-1);
	obj.display();
}


main();

Output

 Head to Tail Nodes : 
-1  1  3  4  5  6  7  10  12  
 Tail to Head Nodes : 
12  10  7  6  5  4  3  1  -1 
/*
 Swift 4 Program
 Sorted insertion in doubly linked list
*/

class Node {
  var data: Int;
  var next: Node? ;
  var prev: Node? ;
  init(_ value: Int) {
    self.data = value;
    self.next = nil;
    self.prev = nil;
  }
}
class LinkedList {
  var head: Node? ;
  var tail: Node? ;
  init() {
    self.head = nil;
    self.tail = nil;
  }
  func insert(_ value: Int) {
    let node: Node? = Node(value);
    if (node == nil) {
      print("Memory overflow\n");
    } else {
      if (self.head == nil) {
        self.head = node;
        self.tail = node;
      } else
      if (self.head!.data >= value) {
        node!.next = self.head;
        self.head!.prev = node;
        self.head = node;
      } else
      if (self.tail!.data <= value) {
        self.tail!.next = node;
        self.tail = node;
      } else {
        var temp: Node? = self.head;
        while (temp != nil && temp!.next != nil && temp!.next!.data < value) {
          temp = temp!.next;
        }
        node!.next = temp!.next;
        if (temp!.next != nil) {
          temp!.next!.prev = node;
        }
        node!.prev = temp;
        temp!.next = node;
      }
    }
  }
  func display() {
    var temp: Node? = self.head;
    if (temp == nil) {
      print("\nEmpty linked list\n");
      return;
    }
    print("\n Head to Tail Nodes : ");
    while (temp != nil) {
      print(temp!.data ,terminator:"  ");
      temp = temp!.next;
    }
    temp = self.tail;
    print("\n Tail to Head Nodes : ");
    while (temp != nil) {
      print(temp!.data ,terminator:"  ");
      temp = temp!.prev;
    }
  }
}

func main() {
  let obj: LinkedList = LinkedList();
  obj.insert(3);
  obj.insert(5);
  obj.insert(7);
  obj.insert(12);
  obj.insert(10);
  obj.insert(6);
  obj.insert(4);
  obj.insert(1);
  obj.insert(-1);
  obj.display();
}
main();

Output

 Head to Tail Nodes : 
-1  1  3  4  5  6  7  10  12  
 Tail to Head Nodes : 
12  10  7  6  5  4  3  1  -1 

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved