|
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:
- Size:
ü
The method size() calculates the size of the
list recursively by counting nodes until null is reached.
- 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.
- 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.
- 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:
- Creates
an empty linked list.
- Adds
elements like "Mandal", "Chandra", and "Java".
- Adds
elements at specific positions using an index.
- Removes
elements by value.
- 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:
- Boundary
Handling:
- In
methods like addAtPosition, it's good to handle cases where the index is
out of bounds more explicitly.
- Efficiency:
- You
might consider iterative versions of some methods for better performance,
though recursion keeps the code elegant.
- 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!
0 Comments