In this article, we will learn what is singly linked list and it's implementation using Java.
The singly linked list is a linear data structure in which each element of the list contains a pointer which points to the next element in the list. Each element in the singly linked list is called a node. Each node has two components: data and a pointer next which points to the next node in the list.
The first node of the list is called as head, and the last node of the list is called a tail. The last node of the list contains a pointer to the null. Each node in the list can be accessed linearly by traversing through the list from head to tail.
Singly Linked List Implementation Using Java
First, we need to create a Node and each node we will store in a singly linked list. Each Node contains two fields, the first field contains data and the second field contains a link to the next node.
Create Node
Following is a type declaration for a linked list:
/**
* Class demonstrates the declaration for a linked list.
* @author Ramesh Fadatare
*
*/
public class ListNode{
public ListNode next;
public int data;
// Creates an empty node.
public ListNode(){
next = null;
data = Integer.MIN_VALUE;
}
// Creates a node storing the specified data.
public ListNode (int data){
next = null;
this.data = data;
}
// Returns the node that follows this one.
public ListNode getNext(){
return next;
}
// Sets the node that follows this one.
public void setNext (ListNode node){
next = node;
}
// Returns the data stored in this node.
public int getData(){
return data;
}
// Sets the data stored in this node.
public void setdata (int elem){
data = elem;
}
// Sets the data stored in this node.
public String toString (){
return Integer.toString(data);
}
}
Operations
Let's write a logic for the below basic operations on a Linked List.
1. Traversing the list
2. Inserting an item into the list
Insertion into a singly-linked list has three cases:
>> Inserting a new node before the head (at the beginning)
>> Inserting a new node after the tail (at the end of the list)
>> Inserting a new node at the middle of the list (random location)
3. Deleting an item from the list
Similar to insertion, here we also have three cases.
>> Deleting the first node
>> Deleting the last node
>> Deleting an intermediate node
Please refer the comments in below program are self-descriptive
Complete program:
package com.javaguides.javads.lists;
/**
* Linked List data structure implementation using Java.
* @author Ramesh Fadatare
*
*/
public class LinkedList {
/** This class has a default constructor: */
public LinkedList() {
length = 0;
}
/** This is the only field of the class. It holds the head of the list */
ListNode head;
/** Length of the linked list. */
private int length;
/** Return the first node in the list. */
public synchronized ListNode getHead() {
return head;
}
/** Insert a node at the beginning of the list. */
public synchronized void insertAtBegin(ListNode node) {
node.setNext(head);
head = node;
length++;
}
/** Insert a node at the end of the list. */
public synchronized void insertAtEnd(ListNode node) {
if (head == null) {
head = node;
} else {
ListNode p, q;
for (p = head; (q = p.getNext()) != null; p = q) {
}
p.setNext(node);
}
length++;
}
/**
* Add a new value to the list at a given position. All values at that
* position to the end move over to make room.
*/
public void insert(int data, int position) {
// fix the position
if (position < 0) {
position = 0;
}
if (position > length) {
position = length;
}
// if the list is empty, make it be the only element
if (head == null) {
head = new ListNode(data);
}
// if adding at the front of the list...
else if (position == 0) {
ListNode temp = new ListNode(data);
temp.next = head;
head = temp;
}
// else find the correct position and insert
else {
ListNode temp = head;
for (int i = 1; i < position; i += 1) {
temp = temp.getNext();
}
ListNode newNode = new ListNode(data);
newNode.next = temp.next;
temp.setNext(newNode);
}
// the list is now one value longer
length += 1;
}
/** Remove and return the node at the head of the list. */
public synchronized ListNode removeFromBegin() {
ListNode node = head;
if (node != null) {
head = node.getNext();
node.setNext(null);
}
return node;
}
/** Remove and return the node at the end of the list. */
public synchronized ListNode getLast() {
if (head == null) {
return null;
}
if (head.getNext() == null) {
return head;
}
ListNode p = head.getNext();
while (p.getNext() != null) {
p = p.getNext();
}
return p;
}
/** Remove and return the node at the end of the list. */
public synchronized ListNode removeFromEnd() {
if (head == null) {
return null;
}
ListNode p = head, q = null, next = head.getNext();
if (next == null) {
head = null;
// reduce the length of the list
length -= 1;
return p;
}
while ((next = p.getNext()) != null) {
q = p;
p = next;
}
q.setNext(null);
// reduce the length of the list
length -= 1;
return p;
}
/**
* Remove a node matching the specified node from the list. Use equals()
* instead of == to test for a matched node.
*/
public synchronized void removeMatched(ListNode node) {
if (head == null) {
return;
}
if (node.equals(head)) {
head = head.getNext();
// reduce the length of the list
length -= 1;
return;
}
ListNode p = head, q = null;
while ((q = p.getNext()) != null) {
if (node.equals(q)) {
p.setNext(q.getNext());
// reduce the length of the list
length -= 1;
return;
}
p = q;
}
}
/**
* Remove the value at a given position. If the position is less than 0,
* remove the value at position 0. If the position is greater than 0, remove
* the value at the last position.
*/
public void remove(int position) {
// fix position
if (position < 0) {
position = 0;
}
if (position >= length) {
position = length - 1;
}
// if nothing in the list, do nothing
if (head == null) {
return;
}
// if removing the head element...
if (position == 0) {
head = head.getNext();
}
// else advance to the correct position and remove
else {
ListNode temp = head;
for (int i = 1; i < position; i += 1) {
temp = temp.getNext();
}
temp.setNext(temp.getNext().getNext());
}
// reduce the length of the list
length -= 1;
}
/**
* Return a string representation of this collection, in the form
* ["str1","str2",...].
*/
public String toString() {
String result = "[";
if (head == null) {
return result + "]";
}
result = result + head.getData();
ListNode temp = head.getNext();
while (temp != null) {
result = result + "," + temp.getData();
temp = temp.getNext();
}
return result + "]";
}
/** Return the current length of the list. */
public int length() {
return length;
}
/**
* Find the position of the first value that is equal to a given value. The
* equals method us used to determine equality.
*/
public int getPosition(int data) {
// go looking for the data
ListNode temp = head;
int pos = 0;
while (temp != null) {
if (temp.getData() == data) {
// return the position if found
return pos;
}
pos += 1;
temp = temp.getNext();
}
// else return -1
return Integer.MIN_VALUE;
}
/** Size of the list. */
public boolean isEmpty() {
return length == 0;
}
/** Remove everything from the list. */
public void clearList() {
head = null;
length = 0;
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.insert(10, 1);
linkedList.insert(20, 2);
linkedList.insert(30, 3);
linkedList.insert(40, 4);
// insert node at bigin of linkedlist
ListNode firstNode = new ListNode();
firstNode.setdata(0);
linkedList.insertAtBegin(firstNode);
// insert node at end of linkedlist
ListNode lastNode = new ListNode();
lastNode.setdata(50);
linkedList.insertAtEnd(lastNode);
System.out.println(" Head of the linked list : " + linkedList.getHead());
System.out.println(" Last of the linked list : " + linkedList.getLast());
System.out.println(" Postion of the node data 10 : " + linkedList.getPosition(10));
// remove node by position
linkedList.remove(1);
// remove node from begin
linkedList.removeFromBegin();
// Remove node from end
linkedList.removeFromEnd();
System.out.println(" Head of the linked list : " + linkedList.getHead());
System.out.println(" Last of the linked list : " + linkedList.getLast());
}
}
Output:
Head of the linked list : 0
Last of the linked list : 50
Postion of the node data 10 : 1
Head of the linked list : 20
Last of the linked list : 40Top Data Structure Tutorial - Data Structures and Algorithms in Java
Comments
Post a Comment
Leave Comment