Singly Linked List

We all use array to store a collection of elements. One of the major disadvantage of using an array is its contiguous memory allocation and static size. Moreover operations like insertion and deletion in an array are highly expensive. For example:- If we have an array of elements as shown below:

Array Disadvantage

Now let us delete an element 5  i.e. element as shown below:

Delete element Array

In such case all the elements after element 5, should be moved to one index before as shown:

Movement of Element in Array while Deletion

Due to such movements in array, array becomes highly expensive datastructure in some cases.

Another way to store collection of elements - using linked list. A linked list/singly linked list is linear collection of data elements called nodes. Each node comprises of 

  • Data Field - Used to store value/element
  • Address Field - used to store address/information of next node.

Hence, for a given set of elements{1,2,3,4,5} linked list can be constructed as

Singly Linked List Design

Let us design linked list data structure in Java -

LinkedList.java

/**
 * @author Amit Gupta
 *
 */
public class LinkedList<T> {

	Node<T> head;
		
	private static class Node<T>{
		T value;
		Node<T> next;
			
		Node(Node<T> next, T value) {
			this.value = value;
			this.next = next;
		}
	}
}

Linked List operations

We can perform following operations in LinkedList

Insert Element in Linked List

To add elements in Linked List we implemented add() method in LinkedList class as shown below:-

LinkedList.java

/**
 * @author Amit Gupta
 *
 */
public class LinkedList<T> {

	Node<T> head;

	private static class Node<T> {

		T value;
		Node next;

		Node(Node<T> next, T value) {
			this.value = value;
			this.next = next;
		}

		public T getValue() {
			return value;
		}

		public void setValue(T value) {
			this.value = value;
		}

		public Node<T> getNext() {
			return next;
		}

		public void setNext(Node<T> next) {
			this.next = next;
		}

		Node(T value) {
			this.value = value;
			this.next = null;
		}

	}

	public void add(T item) {
		Node<T> newNode = new Node<T>(item);
		if (head == null) {
			head = newNode;
		}else{

		Node<T> addNode = head;
		if (addNode != null) {
			while (addNode.getNext() != null) {
				addNode = addNode.getNext();
			}
			addNode.setNext(newNode);
		}
}
	}
}

DemoLinkedList.java :- This program illustrates insertion of elements in LinkedList 

public class DemoLinkedList {

	public static void main(String[] args) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		list.add(5);
		list.add(5);
		list.add(7);
		list.add(8);
		list.add(9);

	}
}

Traversal of Elements in Linked List

To traverse through linked list we have added traverse() method which is used to iterate through the linkedlist till the last node of list. As the last node does not have reference/pointer to next node, the traversal ends to last node. The modified LinkedList.java class will be

LinkedList.java

/**
 * @author Amit Gupta
 *
 */
public class LinkedList<T> {

	Node<T> head;

	private static class Node<T> {

		T value;
		Node next;

		Node(Node<T> next, T value) {
			this.value = value;
			this.next = next;
		}

		public T getValue() {
			return value;
		}

		public void setValue(T value) {
			this.value = value;
		}

		public Node<T> getNext() {
			return next;
		}

		public void setNext(Node<T> next) {
			this.next = next;
		}

		Node(T value) {
			this.value = value;
			this.next = null;
		}

	}

	public void add(T item) {
		Node<T> newNode = new Node<T>(item);
		if (head == null) {
			head = newNode;
		}else{

		Node<T> addNode = head;
		if (addNode != null) {
			while (addNode.getNext() != null) {
				addNode = addNode.getNext();
			}
			addNode.setNext(newNode);
		}
}
	}
public void traverse() {
		Node<T> traversalNode = head;
		while (traversalNode != null) {
			System.out.println(traversalNode.getValue());
			traversalNode = traversalNode.getNext();
		}
	}
}

DemoLinkedList.java

public class DemoLinkedList {

	public static void main(String[] args) {
		LinkedList list = new LinkedList();
		list.add(5);
		list.add(5);
		list.add(7);
		list.add(8);
		list.add(9);
		list.traverse();
	}
}

Output

5
5
7
8
9

Deletion of a particular element in Linked List

To delete a particular element in linked list we have added delete() method in LinkedList.java program in which we have to traverse till we find the element in the linkedlist, once we find the element in linked list we change the link of previous node from current node to next node as shown:

 Delete Element in Linked List

LinkedList.java 

/**
 * @author Amit Gupta
 *
 */
public class LinkedList<T> {

	Node<T> head;

	private static class Node<T> {

		T value;
		Node next;

		Node(Node<T> next, T value) {
			this.value = value;
			this.next = next;
		}

		public T getValue() {
			return value;
		}

		public void setValue(T value) {
			this.value = value;
		}

		public Node<T> getNext() {
			return next;
		}

		public void setNext(Node<T> next) {
			this.next = next;
		}

		Node(T value) {
			this.value = value;
			this.next = null;
		}

	}

	public void add(T item) {
		Node<T> newNode = new Node<T>(item);
		if (head == null) {
			head = newNode;
		}else{

		Node<T> addNode = head;
		if (addNode != null) {
			while (addNode.getNext() != null) {
				addNode = addNode.getNext();
			}
			addNode.setNext(newNode);
		}
}
	}
public void traverse() {
		Node<T> traversalNode = head;
		while (traversalNode != null) {
			System.out.println(traversalNode.getValue());
			traversalNode = traversalNode.getNext();
		}
	}
public void delete(int value) {
		Node<T> cur = head;
		Node<T> prev = null;

		if (head != null && head.getValue().equals(value)) {
			head = head.next;
			return;
		}
		while (cur != null && !cur.getValue().equals(value)) {
			prev = cur;
			cur = cur.next;
		}
		if (prev == null)
			return;

		prev.next = cur.next;
	}
}

DemoLinkedList.java

public class DemoLinkedList {

	public static void main(String[] args) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		list.add(5);
		System.out.println("**Before Deletion**");
		list.traverse();
		list.delete(5);
		System.out.println("**After Deletion**");
		list.traverse();
	}
}

Output

**Before Deletion**
5
6
7
8
9
**After Deletion**
6
7
8
9

In this chapter we learned about singly linked list and various operations like creation of linked list, insertion of element in linked list, traversal of linked list and deletion of element in linked list in Java.


Share this chapter
Comments
comments powered by Disqus

Navigation

Social Media