LinkedList in java - codingtube

A linked list in java works by creating a collection of objects (nodes) which both carry the data we want to store and a reference to the next node in the list

A linked list is fundamentally different way of storing collections

Creating a Linked List The Node Class

The class has two constructors that combine with the new operator to create a node. The default constructor initializes each instance variable to be null. The constructor with an type parameter initializes the nodeValue field and sets next to null.

Table of Contents

Properties of LinkedList in java

in LinkedList no fixed size; grow one element at a time
space overhead in LinkedList
- each element must store an additional reference
- Size = n x sizeof (element) + n x sizeof(reference)

no easy access to i-th element wrt the head of the list
- need to hop through all previous elements
Search for class Java LinkedList
Has all expected methods and features

There is more than one type of a linked list. Some different type of linked list are

Singly linked list

Root node links one way through all the nodes. Last node links to NULL

Doubly linked list

Every nodes stores a reference to its previous node as well as its next. Last node links to NULL

Circular linked list

Circular linked list have a reference to one node which is the tail node and all the nodes are linked together in one direction forming a circle

Creating a Linked List The Node Class

public class Node<T>
{
// data held by the node
public T nodeValue;
// next node in the list
public Node<T> next;
// default constructor with no initial value
public Node()
{
nodeValue = null;
next = null; }
// initialize nodeValue to item and set next to null
public Node(T item)
{
nodeValue = item;
next = null;
}
}

LinkedList methods

Method’s name	Method’s description
List()	Constructor builds an empty linked list
boolean isEmpty()	Returns true if this list is empty and false otherwise
Node getFirst()	Returns the reference to first element in this list. If list is empty returns nul
Node insert(Node pos, T x)	Inserts the type T element x after the specified position pos in this list and returns the reference to inserted element x.
Node remove(Node pos)	Removes the first occurrence of the specified element pos in this list and returns the next element position. We assume that pos != null
String to String()	Returns the string representation of linked list.

LinkedList methods

Programme to implement single LinkedList

Node.java

public class Node 
{
	int data;
	Node next;
}

LinkedList


public class LinkedList 
{
	Node head;
	
	public void insert(int data)
	{
		Node node = new Node();
		node.data = data;
		node.next = null;
		
		if(head==null)
		{
			head = node;
		}
		else
		{
			Node n = head;
			while(n.next!=null)
			{
				n = n.next;
			}
			n.next =  node;
		}
		
	}
	public void insertAtStart(int data)
	{
		Node node = new Node();
		node.data = data;
		node.next = null;
		node.next = head;
		head = node;
	}
	
	public void insertAt(int index,int data)
	{
		Node node = new Node();
		node.data = data;
		node.next = null;
		
		if(index==0)
		{
			insertAtStart(data);
		}
		else{
		Node n = head;
		for(int i=0;i<index-1;i++)
		{
			n = n.next;
		}
		node.next = n.next;
		n.next = node;
		}
	}
	
	public void deleteAt(int index)
	{
		if(index==0)
		{
			head = head.next;
		}
		else
		{
			Node n = head;
			Node n1 = null;
			for(int i=0;i<index-1;i++)
			{
				n = n.next;
			}
			n1 = n.next;
			n.next = n1.next;
			//System.out.println("n1 " + n1.data);
			n1 = null;
		}
	}
	
	public void show()
	{
		Node node = head;
		
		while(node.next!=null)
		{
			System.out.println(node.data);
			node = node.next;
		}
		System.out.println(node.data);
	}
}

Runner.java

public class Runner {

	public static void main(String[] args) {
		
		LinkedList list = new LinkedList();
		list.insert(18);
		list.insert(45);
		list.insert(12);
		list.insertAtStart(25);
		
		list.insertAt(0, 55);
		
		list.deleteAt(2);
		
		list.show();
	}

}