Linked List

As we know that Array is very useful data structure but it has certain limitations:

1. changing the size of the array requires creating a new array and then copying all data from the array with the old size to the array with the new size and
2. the data in the array are next to each other sequentially in memory, which means that inserting or deleting an item inside the array requires shifting some other data in this array.

This limitation can be overcome by using linked structures. Linked lists is a simple data structure which contains individual elements(say nodes) with links between them and the nodes are arranged in a linear order. Each node in a linked list contains a reference (or link) to the next node. As compared to Array, Linked List has some advantage- Linked list is unbounded, deletion of an element is faster because only you have to change some links, there is no shifting of elements. You can use a linked list in many cases in which you use an array, unless you need frequent random access to individual items using an index.

Types of Linked List

• • Singly Linked List: If a node has a link only to its successor in a Linked List, then the list is called a singly linked list. A node includes two data fields: info and next. The info field is used to store information, and this field is important to the application. The next field is used to link together nodes to form a linked list. Last node point to null.
    

Java implementation of Singly Linked List

Create a Node class first which will keep info and link to the next element.

public class Node {

	int info;
	Node next;

	public Node(int info) {
		this.info = info;
	}

	public void displayNode() {
		System.out.print("[" + info + "]->;");
	}
}

Create LinkList class which will hold nodes.

public class LinkList {

	private Node first;
	
	public LinkList() {
		first = null;
	}
        public Boolean isEmpty(){
                return first == null;
        }
	public void insertFirst(int info) {
		Node node = new Node(info);
		node.next = first;
		first = node;
	}

	public void insertLast(int info) {
		Node node = new Node(info);
		if (first == null) {
			first = node;
		} else {
			Node current = first;
			while (current.next != null) {
				current = current.next;
			}
			current.next = node;
		}
	}

	public boolean delete(int info) {
		assert isEmpty(): "Empty list";
		// if it is the first element then move first one element further
		if (first.info == info) {
			first = first.next;
			return true;
		} else {
			Node current = first;
			Node previous = first;
			while (current != null && current.info != info) {
				previous = current;
				current = current.next;
			}
			if (current != null) {
				previous.next = current.next;
				return true;
			} else {
				System.err.println("No match found in the list for value:"+ info);
				return false;
			}
		}
	}

	public Node find(int info) {
		assert isEmpty(): "Empty list";
		Node current = first;
		while (current != null && current.info != info) {
			current = current.next;
		}
		if (current != null) {
			return current;
		} else {
			System.err.println("No match found in the list for value:" + info);
			return null;
		}
	}

	public void displayList() {
		Node current = first;
		while (current != null) {
			current.displayNode();
			current = current.next;
		}
		System.out.println();
	}

	public static void main(String[] args) {
		LinkList linkedList1 = new LinkList();
		linkedList1.insertFirst(5);
		linkedList1.insertFirst(10);
		linkedList1.insertFirst(15);
		linkedList1.insertFirst(20);
		System.out.println("First List-");
		linkedList1.displayList();
		linkedList1.delete(15);
		System.out.println("After deleting 15-");
		linkedList1.displayList();

		LinkList linkedList2 = new LinkList();
		linkedList2.insertLast(5);
		linkedList2.insertLast(10);
		linkedList2.insertLast(15);
		linkedList2.insertLast(20);
		System.out.println("Second List-");
		linkedList2.displayList();
		linkedList2.delete(5);
		System.out.println("After deleting first element 5-");
		linkedList2.displayList();

	}
}
Output
-------
First List-
[20]->[15]->[10]->[5]->
After deleting 15-
[20]->[10]->[5]->
Second List-
[5]->[10]->[15]->[20]->
After deleting first element 5-
[10]->[15]->[20]->

Let’s understand each methods in detail.
insertFirst(): This method insert a new node at the beginning of the list. This is very simple – create a new Node to insert and points its next to the old first, now you have new Node at the start so make it first. Using insert first you can create a Stack. It take O(1) time.

insertLast(): This method insert a new node at the end of the list. You traverse the whole list to reach at the last position. Point the next pointer of last to the new Node. It takes O(n) time where n is the current size of the list.

delete(): Delete the Node of given value. If the first Node contain the value then just move first to the next element of first else traverse the list to find the Node, maintain current and previous pointer where previous will point to the previous Node of current. After finding node just point previous->next to current->next. In worst case it will take O(n) time where the element is at the last position or there is no such element in list.

find(): This method traverse the list and match each Node value to the given value, if match is found it return the Node. In worst case it will take O(n) time where the element is at the last position or there is no such element in list.

Go to the next page – Click on the below red circle with page number.