Find Middle & Reverse a Custom Linked List Using Iteration

java

public class LinkedListDemo {
public static void main(String args[]) {
System.out.println("..................................................");
System.out.println("---------------------------String-----------------");
System.out.println("..................................................");
LinkedListMidElement<String> cc=new LinkedListMidElement<String>();
cc.add("data5");
cc.add("data6");
cc.add("data7");
cc.add("data8");
cc.add("data9");
cc.add("data1");
cc.add("data2");
cc.add("data3");
cc.add("data4");
cc.displayLinkedList();
cc.findMiddle();
cc.reverseDisplay();
System.out.println("..................................................");
System.out.println("---------------------------Integer-----------------");
System.out.println("..................................................");
LinkedListMidElement<Integer> integer=new LinkedListMidElement<Integer>();
integer.add(5);
integer.add(6);
integer.add(7);
integer.add(8);
integer.add(9);
integer.add(1);
integer.add(2);
integer.add(3);
integer.add(4);
integer.displayLinkedList();
integer.findMiddle();
integer.reverseDisplay();
}
}

Step 2>

public class LinkedListNode<T> {
    public T data; // data in Node.
    public LinkedListNode<T> next;
    // points to next Node in list.

    /**
    * Constructor
    */
    public LinkedListNode(T data){
    this.data = data;
    }
    /**
    * Display Node's data
    */
    public void displayNode() {
    System.out.print( data + " ");
    }
}

Step 3>
public class LinkedListMidElement<T> {

private LinkedListNode<T> first;

/**
  * generic Single LinkedList constructor
  */
public LinkedListMidElement() {
first = null;
}

/**
  * Insert New Node at first position of generic Single LinkedList
  */
public void add(T data) {
LinkedListNode<T> newNode = new LinkedListNode<T>(data); // Creation of
                 // New Node.
newNode.next = first; // newLink ---> old first
first = newNode; // first ---> newNode
}

/**
  * Deletes first Node of generic Single LinkedList
  */
public LinkedListNode<T> deleteFirst() {
if (first == null) { // means LinkedList in empty, throw exception.
}
LinkedListNode<T> tempNode = first; // save reference to first Node in
// tempNode- so that we could return saved reference.
first = first.next; // delete first Node (make first point to second
       // node)
return tempNode; // return tempNode (i.e. deleted Node)
}

/**
  * Display generic Single LinkedList
  */
public void displayLinkedList() {
System.out.print("Displaying LinkedList [first--->last]: ");
LinkedListNode<T> tempDisplay = first; // start at the beginning of
System.out.println();        // linkedList
while (tempDisplay != null) { // Executes until we don't find end of
          // list.
   tempDisplay.displayNode();
   tempDisplay = tempDisplay.next; // move to next Node
}
System.out.println();
}

/**
  *
  * @return
  */
public T findMiddle() {
LinkedListNode<T> head = first;
LinkedListNode<T> current = head;
int length = 0;
LinkedListNode<T> middle = head;
while (current.next != null) {
length++;
   if (length % 2 == 0) {
    middle = middle.next;
   }
   current = current.next;
}
System.out.println("Mid Element of Linked List : "+middle.data);
return middle.data;
}

public void reverseDisplay(){
System.out.print("Displaying LinkedList in reverse order [last--->first]: ");
System.out.println();
LinkedListNode<T> reverseDisplay = reverse(first); // start at the beginning of
    // linkedList
while (reverseDisplay != null) { // Executes until we don't find end of
// list.
   reverseDisplay.displayNode();
   reverseDisplay = reverseDisplay.next; // move to next Node
}
System.out.println();
}
/**
  *
  * @param node
  * @return
  */
public LinkedListNode<T> reverse(LinkedListNode<T> node) {
   LinkedListNode<T> prev = null;
   LinkedListNode<T> current = node;
   LinkedListNode<T> next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}

}

This Java code demonstrates a generic singly linked list that supports adding elements, finding the middle element, and reversing the list. Here's a breakdown of the key components:

1. LinkedListNode<T> Class:

Represents a single node in the linked list.
Contains a generic data field to hold the node's value and a next pointer to the next node in the list.
Provides a displayNode method to print the node's data.

2. LinkedListMidElement<T> Class:

Manages the linked list operations like adding elements, finding the middle element, and reversing the list.

Key Methods:

add(T data):

Adds a new node at the beginning of the list.
The new node becomes the first node, and its next pointer references the old first node.

deleteFirst():

Removes the first node from the list and returns it.
The first pointer is updated to reference the second node.

displayLinkedList():

Iterates through the list from the first node to the end, printing each node's data.

findMiddle():

Finds and returns the middle element of the list.
Uses two pointers: one (current) to traverse the list and the other (middle) to track the middle node.
The middle pointer is advanced every second step, ensuring it ends up in the middle by the time the traversal is complete.

reverseDisplay():

Displays the linked list in reverse order by first reversing the list using the reverse method and then iterating through the reversed list.

reverse(LinkedListNode<T> node):

Reverses the linked list by iterating through it and adjusting the next pointers.
The prev pointer becomes the new head of the reversed list.

3. LinkedListDemo Class:

This is the main driver class where instances of LinkedListMidElement are created for different data types (String and Integer).
Demonstrates adding elements, finding the middle element, displaying the list in normal and reverse order.

Sample Output:

When you run the LinkedListDemo class, it will produce output similar to this:

Out put

..................................................

---------------------------String-----------------

..................................................

Displaying LinkedList [first--->last]:

data4 data3 data2 data1 data9 data8 data7 data6 data5

Mid Element of Linked List : data1

Displaying LinkedList in reverse order [last--->first]:

data5 data6 data7 data8 data9 data1 data2 data3 data4

..................................................

---------------------------Integer-----------------

..................................................

Displaying LinkedList [first--->last]:

4 3 2 1 9 8 7 6 5

Mid Element of Linked List : 1

Displaying LinkedList in reverse order [last--->first]:

5 6 7 8 9 1 2 3 4

Notes:

Efficiency: The findMiddle method is efficient with a time complexity of O(n), as it traverses the list only once.
Generic Support: The linked list is generic, allowing it to store any type of data.
Reversing the List: The reverseDisplay method actually reverses the list, which might not be what you want if you only need to print in reverse. You can create a stack-based or recursive solution if you want to avoid altering the list.