Linked List Introduction and it's Implementation - The Coding Shala

Home >> Data Structures >> Linked List Introduction and its Implementation

 In this post, we will learn what is linked list data structure and will implement a singly linked list in Java.

Linked List Data Structure

A linked list is a linear data structure. The linked list is a chain of Nodes that are connected using pointers. One Node contains the data/element and a pointer called next that points to the next node. Unlike arrays, linked list elements are not stored in a contiguous location. There are different types of the linked lists like a singly linked list, doubly linked list, and circular linked list. Here we will cover a singly linked list.
Singly Linked List - The Coding Shala

The following are main terms used in a linked list:
  • head: front node of a linked list
  • next: pointer to the next node
  • node: contains data/value and the next pointer
We can create a linked list of different data types like integer, string, etc.

Advantages and Disadvantages of linked lists

The following are some advantages and disadvantages of the linked list:
  • The size of linked lists is not fixed. We can add or remove nodes as per our requirements.
  • Addition and deletion are easy in the linked list. We can do it in O(1) time.
  • Like arrays, random access is not possible in the linked list. We need to traverse the linked list to reach the node.

Implementation of singly linked list

The following is the structure of a linked list in Java: 

// structure of Node
class Node {
	int data;
	Node next;
	
	Node (int data) {
		this.data = data;
	}
}

Refer to the below full Java program to create and traverse a linked list:

// Java program to Implement Singly Linked List
// The Coding Shala 


// structure of Node
class Node {
	int data;
	Node next;
	
	Node (int data) {
		this.data = data;
	}
}

class SinglyLinkedList {
	
	// print linked list
	void printList (Node head) {
		System.out.println("Singly Linked List is: ");
		while (head.next != null) {
			System.out.print(head.data + " -> ");
			head = head.next;
		}
		System.out.println(head.data);
	}
}


public class Main {
	public static void main(String[] args) { 
		Node head = new Node(5);
		Node second = new Node(6);
		Node third = new Node(7);
		
		// connect nodes
		head.next = second;
		second.next = third;
		
		SinglyLinkedList list = new SinglyLinkedList();
		list.printList(head);
	}
}

Linked List Time Complexity

Search: O(n)
Insert: O(1)
Deletion: O(1)


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Single Number 3 LeetCode Solution - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Java Method Overloading - The Coding Shala