Insertion in LinkedList at start and at end with examples.

Our LinkedList class looks something like this. It has a Node Class as a inner class which has a next reference to a Node and a integer value. It also has a head Node variable which can be used for various LinkedList operations. It also has a toString method which parses the LinkedList and returns a comma separated value. We will explore this class in other examples.

public class LinkedList {
        class Node{
		int value;
		Node next;
		public Node(int x){
			value=x;
		}
	}
	Node head;

	@Override
	public String toString() {
		StringBuffer strbuf=new StringBuffer();
		if (head!=null){
			Node n=head;
			strbuf.append(n.value);
			while (n.next!=null){
				strbuf.append(","+n.next.value);
				n=n.next;
			}
		}
		else return null;
		return strbuf.toString();
	}
}

1. Insertion at end
Insertion at end is pretty simple. You need to check if the head is null, if yes then the node being inserted becomes the head. Else you would just parse the list to the last node and set its next reference to the node being inserted. Method with Example and output below

/**
 * Insertion at the beginning
 * @param n : Node to be inserted
 */
public void insertAtStart(Node n) {
	if (head==null){
		head=n;
	}
	else{
		n.next=head;
		head=n;
	}
}

public static void main(String[] args) {
	LinkedList linkedList=new LinkedList();
	linkedList.insertAtStart(linkedList.new Node(2));
	linkedList.insertAtStart(linkedList.new Node(3));
	linkedList.insertAtStart(linkedList.new Node(1));
	linkedList.insertAtStart(linkedList.new Node(6));
	System.out.println(linkedList);
}

Output is

6,1,3,2


2. Insertion at beginning.
This is also very simple. You just need to make the node being inserted as head and point its next reference to the existing head Node. Method with Example and output below

/**
 * Insertion at the end
 * @param n : Node to be inserted
 */
public void insertAtEnd(Node n) {
	if (head==null){
		head=n;
	}
	else{
		Node i=head;
		while(i.next!=null){
			i=i.next;
		}
		i.next=n;
	}
}

public static void main(String[] args) {
	LinkedList linkedList=new LinkedList();
	linkedList.insertAtEnd(linkedList.new Node(2));
	linkedList.insertAtEnd(linkedList.new Node(3));
	linkedList.insertAtEnd(linkedList.new Node(1));
	linkedList.insertAtEnd(linkedList.new Node(6));
	System.out.println(linkedList);
}

Output is

2,3,1,6

 

Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself