Header Ads Widget

Responsive Advertisement

Linked List Display By Recursive With Generic Class


package com.kartik;

 

/**

*

@author Kartik Mandal

Blog https://www.javatherapy.in

* A singly-linked list is an algorithm that puts elements of a list in a certain order

* This will display the linked list data where I mentioned generic class of Linked list and class itself recursive.

@date Feb 25, 2015

*/

public class LinkedListRec<E> {

// here, include the LinkedNode definition

private static class LinkedNode<T> {

private T item;

private LinkedNode<T> next;

/**

* constructor to build a node with no successor

@param the value to be stored by this node

*/

private LinkedNode(T value) {

item = value;

next = null;

}

 

/**

* constructor to build a node with specified (maybe null) successor

@param the value to be stored by this node

@param the next field for this node

*/

private LinkedNode(T value, LinkedNode<T> reference) {

item = value;

next = reference;

}

}

// end of the LinkedNode definition

// this is the start of the linked list. If the list is empty, it is null

protected LinkedNode<E> head;

/**

* initializes an empty linked list

*/

public LinkedListRec() {

head = null;

}

 



/** recursive private method, called by the public wrapper method

@param the head of the list (may be null if we are at the end)

@return the size of the list

*/

private int size(LinkedNode<E> current) {

if (current == null) {

return 0; // an empty list has size 0

} // a non-empty list has size 1 more than the rest of the list:

return 1 + size (current.next);

}

/** public wrapper method, calls the private recursive method

@param none

@return the size of the list

*/

public int size() {

return size(head);

}

 

/** recursive private method, called by the public wrapper method

@param the head of the list (may be null if we are at the end)

@param the value to be added

@return the list, with the value added

*/

private LinkedNode<E> addAtEnd(LinkedNode<E> node, E value) {

if (node == null) {

return new LinkedNode<E>(value);

}

node.next = addAtEnd(node.next, value);

return node;

}

/** public wrapper method, calls the private recursive method

@param the value to be added at the end of the linked list

*/

public void add(E value) {

head = addAtEnd(head, value);

}

/** recursive private method, called by the public wrapper method

@param the head of the list (may be null if we are at the end)

@param the number of nodes to skip before inserting

@param the value to be added

@return the list, with the value added

*/

private LinkedNode<E> addAtPosition(LinkedNode<E> node, int skip, E value) {

if (skip == 0) {

return new LinkedNode<E>(value, node);



}

if (node == null) { // node is null but skip > 0 -- bad index

throw new IndexOutOfBoundsException("bad index for add");

}

node.next = addAtPosition(node.next, skip - 1, value);

return node;

}

/** public wrapper method, calls the private recursive method

@param the position at which to add: 0 to add at the start

@param the value to be added

@throws IndexOutOfBoundsException if the index is less than 0

* or greater than the number of elements in the linked list

*/

public void add(int index, E value) {

head = addAtPosition(head, index, value);

}

 

/** recursive private method, called by the public wrapper method

@param the head of the list (may be null if we are at the end)

@param the value to be removed

@return the list, with the value removed

*/

private LinkedNode<E> remove(LinkedNode<E> node, E value) {

if (node == null) { // node is null but skip > 0 -- bad index

return node;

}

if (node.item.equals(value)) {

return node.next; // match, so remove this node

}

node.next = remove(node.next, value);

return node;

}

 

/** public wrapper method, calls the private recursive method

@param the object to remove

*/

public void remove(E value) {

head = remove(head, value);

}

 

 

/** recursive private method, called by the public wrapper method

@param the head of the list (may be null if we are at the end)

@return the string representing the list

*/

private String toString(LinkedNode<E> node) {

if (node == null) {

return "";

}

if (node.next == null) {

return node.item.toString();

}

return node.item.toString() + " ==> " + toString(node.next);

}

 

/**

* concatenates the elements of the linked list, separated by " ==> "

@return the string representation of the list

*/

public String toString() {

return toString(head);

}

 

/**

* unit test method -- basic testing of the functionality

@param required, ignored

*/

public static void main (String [] arguments) {

LinkedListRec<String> ll = new LinkedListRec<String>();

System.out.println (ll);

ll.add("Mandal");

System.out.println (ll);

ll.add(1, "Chandra");

System.out.println (ll);

ll.add("Java");

System.out.println (ll);

ll.add(0, "hello");

System.out.println (ll);

ll.add("foo");

ll.add("baz");

ll.add(0, "hello");

System.out.println (ll);

ll.remove ("foo"); // remove an intermediate element

System.out.println (ll);

ll.remove ("hello"); // remove the first element

System.out.println (ll);

ll.remove ("baz"); // remove the last element

System.out.println (ll);

ll.add("Kartik");

System.out.println (ll);

}

}

 

 

 

LinkedListRec class is a recursive implementation of a singly linked list that supports basic operations like adding, removing elements, and displaying the list as a string. Here's a breakdown of how it works:

Structure:

Ø  Node Class:

ü  The LinkedNode<T> class represents a node in the linked list, holding an item and a reference to the next node.

ü  Two constructors are provided, one to create a node without a successor and one to create a node with a specified successor.

Ø  Linked List Class:

ü  The LinkedListRec<E> class contains a reference to the head of the list (head).

ü  Various methods operate recursively on the list, using helper methods to manipulate nodes.

Operations:

  1. Size:

ü  The method size() calculates the size of the list recursively by counting nodes until null is reached.

  1. Adding Elements:

ü  add(E value): Adds an element at the end of the list.

ü  add(int index, E value): Adds an element at a specific position. The recursive function ensures that nodes are skipped correctly.

  1. Removing Elements:

ü  remove(E value): Removes the first occurrence of a given element. It finds the node with a matching value and bypasses it by returning its successor.

  1. String Representation:

ü  toString(): Converts the linked list into a string where the elements are separated by " ==> ".

Example Execution:

Here’s what happens in the main method step by step:

  1. Creates an empty linked list.
  2. Adds elements like "Mandal", "Chandra", and "Java".
  3. Adds elements at specific positions using an index.
  4. Removes elements by value.
  5. Prints the current state of the list at various stages.

Sample Output:

When you run the main method, the output will look something like this (depending on the internal operations):

text

// Initial empty list

// After adding "Mandal"

Mandal

// After adding "Chandra" at index 1

Mandal ==> Chandra

// After adding "Java" at the end

Mandal ==> Chandra ==> Java

// Adding "hello" at index 0

hello ==> Mandal ==> Chandra ==> Java

// After adding more elements

hello ==> Mandal ==> Chandra ==> Java ==> foo ==> baz

// Removing "foo"

hello ==> Mandal ==> Chandra ==> Java ==> baz

// Removing "hello"

Mandal ==> Chandra ==> Java ==> baz

// Removing "baz"

Mandal ==> Chandra ==> Java

// Adding "Kartik"

Mandal ==> Chandra ==> Java ==> Kartik

 

We need to do below three Improvements & Suggestions:

  1. Boundary Handling:
    • In methods like addAtPosition, it's good to handle cases where the index is out of bounds more explicitly.
  2. Efficiency:
    • You might consider iterative versions of some methods for better performance, though recursion keeps the code elegant.
  3. Null Handling:
    • Ensure you handle null values appropriately, especially for the remove method, to avoid NullPointerException.

This implementation provides a clean and functional recursive solution for a singly linked list!


Post a Comment

0 Comments