Present an algorithm (in outline form) for inserting an element into a sorted li

Question

Present an algorithm (in outline form) for inserting an element into a sorted linked list so that the list is always in sorted order. Do not utilize a sorting routine, but rather devise an insert (add) algorithm that will search the list and insert the new element in the proper place in the list so that the list is always in order. Assume that the objects involved all properly override both the equals (==) and the compareTo (>, <, >=, and <=) methods. The list is to be maintained in ascending order. Assume that the add method has the following signature. public void Add(E element) C#

Explanation / Answer

Given below is the code assuming you have a inner Node class like

class Node
{
E data;
Node next;

public Node(E val)
{
data = val;
next = null;
}
}

================
public void Add(E element)
{
//create a new node and set data and link part
Node n = new Node(element);

if(head == null) //is list empty?
head = n;
else
{
Node curr = head;
Node prev = null;

//find a node before which the new node should be inserted
while(curr != null)
{
if(element.compareTo(curr.data) < 0) //if new data is smaller than current node in list, we have found the place to insert
break;
  
prev = curr;
curr = curr.next;
}

n.next = curr; //set the new node's next to the node before which we will insert
if(curr == head) //insert before head node?
head = n;
else
prev.next = n; //link the previous node to the new node
}
  
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.