Singly Linked List Implementation

Linked List- As the name suggests it’s a list which is linked.

    • Linked List consist of Nodes

Nodes are nothing but objects of a class and each node has data and a link to the next node.

class Node {
	public int data;
	public Node next;

	public Node(int data) {
		this.data = data;
		this.next = null;
	}
}
Node
Node

  • The last node in the list points to NULL , so when you reach there you will know that the list ends here.
Linked List
Linked List

Operations:

Add at the Start : Add a node the beginning of the linked list. Its O(1).

Add at the End : Add a node at the end of the linked list. its O(n) since to add a node at the end you need to go till the end of the array.

Delete at the Start : Delete a node from beginning of the linked list. Its O(1).

Delete at the End : Delete a node from the end of the linked list. its O(n) since to delete a node at the end you need to go till the end of the array.

Get Size: returns the size of the linked list.

Get Element at Index : Return the element at specific index, if index is greater than the size then return -1. its O(n) in worst case.

Add Element at Specific Index : Add element at specific index. If index is greater than size then print “INVALID POSITION”. Worst case its O(n)

Display(): Prints the entire linked list. O(n).

Complete Code:

public class LinkListImplementation {
public static void main(String[] args) throws java.lang.Exception {
LinkedListT a = new LinkedListT();
a.addAtBegin(5);
a.addAtBegin(15);
a.addAtEnd(20);
a.addAtEnd(21);
a.deleteAtBegin();
a.deleteAtEnd();
a.addAtIndex(10, 2);
a.addAtEnd(15);
a.display();
System.out.println("\n Size of the list is: " + a.size);
System.out.println(" Element at 2nd position : " + a.elementAt(2));
System.out.println(" Searching element 20, location : " + a.search(15));
}
}
class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedListT {
public Node head;
public int size;
public LinkedListT() {
head = null;
}
public void addAtBegin(int data) {
Node n = new Node(data);
n.next = head;
head = n;
size++;
}
public int deleteAtBegin() {
int tmp = head.data;
head = head.next;
size;
return tmp;
}
public void deleteAtEnd() {
Node currNode = head;
if (head.next == null) {
head = null;
} else {
while (currNode.next.next != null) {
currNode = currNode.next;
}
int temp = currNode.next.data;
currNode.next = null;
size;
}
}
public void addAtEnd(int data) {
if (head == null) {
addAtBegin(data);
} else {
Node n = new Node(data);
Node currNode = head;
while (currNode.next != null) {
currNode = currNode.next;
}
currNode.next = n;
size++;
}
}
public int elementAt(int index){
if(index>size){
return 1;
}
Node n = head;
while(index1!=0){
n=n.next;
index;
}
return n.data;
}
public int getSize(){
return size;
}
public int search(int data){
Node n = head;
int count = 1;
while(n!=null){
if(n.data==data){
return count;
}else{
n = n.next;
count++;
}
}
return 1;
}
public void addAtIndex(int data, int position){
if(position == 1){
addAtBegin(data);
}
int len = size;
if (position>len+1 || position <1){
System.out.println("\nINVALID POSITION");
}
if(position==len+1){
addAtEnd(data);
}
if(position<=len && position >1){
Node n = new Node(data);
Node currNode = head; //so index is already 1
while((position2)>0){
System.out.println(currNode.data);
currNode=currNode.next;
position;
}
n.next = currNode.next;
currNode.next = n;
size++;
}
}
public void display() {
System.out.println("");
Node currNode = head;
while (currNode != null) {
System.out.print("->" + currNode.data);
currNode = currNode.next;
}
}
}

Output:

->5->10->20->15
Size of the list is: 4
Element at 2nd position : 10
Searching element 20, location : 4