Program to reverse a linked list in Java

Question

I have written the following code, in which method rev(list,list) is not working. Please help me determine what's wrong.

import java.io.*;
public class list
{
    int d;
    list l;
    list()
    {
        d=0;
        l=null;
    }

    void create()throws IOException
    {
        int n;// store number of nodes
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter the first data");
        this.d=Integer.parseInt(br.readLine());
        System.out.println("Enter number of nodes to be made");
        n=Integer.parseInt(br.readLine());
        list temp;
        list ptr=this;
        for(int i=1;i<n;i++)
        {
            temp=new list();
            System.out.println("Enter the next data");
            temp.d=Integer.parseInt(br.readLine());
            temp.l=null;
            ptr.l=temp;
            temp=null;
            ptr=ptr.l;
        }
    }

    void delete(list lst, int n)
    {
        list ptr=lst;
        list ptr1=ptr;
        int c=1;
        while(c<n)
        {
            ptr1=ptr;
            ptr=ptr.l;
            c++;
        }
        ptr1.l=ptr.l;
        ptr.l=null;
        ptr=null;
        ptr1=null;
    }

    void insertmid(list lst,int x, int n)
    {
        list temp=new list();
        temp.d=x;
        temp.l=null;
        list ptr=lst;
        int c=1;
        while(c<n)
        {
            ptr=ptr.l;
            c++;
        }
        temp.l=ptr.l;
        ptr.l=temp;
    }

    void rev(list lst,list lst1)
    {

        lst1=null;
        list ptr=new list();

        while(lst!=null)
        {
            ptr =lst;
            lst=lst.l;
            ptr.l=lst1;
            lst1=ptr;

        }
    }


    void display()
    {
        list ptr=this;

        while(ptr!=null)
        {
            System.out.print(ptr.d+"\t");
            ptr=ptr.l;
        }
        System.out.println();
    }

    public static void main(String args[])throws IOException
    {
        list l2=new list();
        list l3=new list();

        l2.create();
        l2.display();
        l2.insertmid(l2,14,2);
        l2.display();
        l2.delete(l2, 3);
        l2.display();
        l2.rev(l2,l3);
        l2.display();

    }
}

Answer 1

First thing you should do is get yourself familiar with Java Naming Conventions because it will make your code cleaner and more understandable. Your current code doesn't distinguish between classes or methods or variables.

Secondly, it seems like you are coming from a C++ background and don't know that Java always passes by value

Here is one thing you are doing that makes no sense:

void rev(list lst,list lst1)
{

    lst1=null;  // this is pointless, essentially, you are using a passed argument as a local variable. 
    // ...

The code bellow is practically equivalent:

void rev(list lst)
{

    list lst1=null; //just create lst1 right here, don't need to pass it in as a parameter
    // ...

Now, I will not go into cleaning your whole code but I will give you the algorithm to reverse a Linked List that you can incorporate into your program:

public Node reverseList(Node head) {
    Node newHead = null;        // New head of the reversed list
    Node prev, curr, next;      // Tracker pointers to previous, current and next node
    prev = null;
    curr = head;
    next = null;
    while(curr != null) {       // Iterate through the list
        next = curr.next;       // Remember the next node
        curr.next = prev;       // Point the current node to the previous
        prev = curr;            // Update the previous node tracker to the current node
        curr = next;            // Update the current node tracker to the next node
        if(next == null) {      // If we reached list end, store the new head
            newHead = prev;
        }
    }
    return newHead;
}

Answer 2

You Can Try this using Java Collection classes:

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

class ReverseList {
List<Integer>list=new LinkedList<Integer>();

public void initializeList(){
    Scanner in=new Scanner(System.in);
    System.out.println("Enter number of nodes:");
    int no=Integer.parseInt(in.next());

    for(int i=0;i<no;i++){
        list.add(Integer.parseInt(in.next()));
    }
    in.close();
}

public void displayList(){
    System.out.println(list);
}

public void reverseList(){
    List<Integer>list2=new LinkedList<Integer>();

    for(int i=list.size()-1;i>=0;i--){
        list2.add(list.get(i));
    }
    this.list=list2;

}

public static void main(String[] args) {
    ReverseList rl1=new ReverseList();
    rl1.initializeList();
    rl1.displayList();
    rl1.reverseList();
    rl1.displayList();
}
}

Answer 3

Please, please follow standard naming conventions. Doing so will make your code much easier to read. In particular, the names of reference types (classes and interfaces) should begin with capital letters (e.g. List) whereas the names of methods and instance variables should begin with lowercase letters.

Here are some comments on your non-working method:

void rev(list lst,list lst1)
{

It is pointless to pass lst1 if you are immediately going to discard whatever value was passed, as you do here:

    lst1=null;

It is also pointless to initialize variable 'ptr' here, as the very first thing you do with it (at the beginning of the loop) is assign a new value. In fact, it would be cleaner to declare it inside the loop body.

    list ptr=new list();

The following loop looks like it's probably ok, but consider the state in which it leaves the object initially referenced by the lst. Hint: lst1 is initialized to null.

    while(lst!=null)
    {
        ptr =lst;
        lst=lst.l;
        ptr.l=lst1;
        lst1=ptr;
    }

Now consider that Java has only pass-by-value, so whatever references are passed to this method are not changed from the invoker's perspective.

}

If you're still not seeing it, then consider this question: which node is now at the head of the list?

In a more general sense, you have a bit of a modelling problem in that your list class tries to do double duty representing not only an overall list but also a node in that list. That can work, and it has properties that could be useful, but it also has properties that can cause trouble. For instance, you cannot represent an empty list with an instance of your class. You also cannot usefully reverse a list represented by an instance of your class via a method having the signature of your rev().

Answer 4

Using Java Class Naming Convention i prepared and rewrote Your code to work as You asked:

import java.io.*;
public class List
{
    private Integer data;
    private List next;

    List(Integer data, List next){
        this.data = data;
        this.next = next;
    }

    List(){
        this(0);
    }

    List(Integer data) {
        this(data, null);
    }

    List(List list) {
        this(list.getData(), list.getNext());
    }

    public void setData(Integer data) {
        this.data = data;
    }

    public Integer getData() {
        return this.data;
    }

    public void setNext(List next) {
        this.next = next;
    }

    public List getNext() {
        return this.next;
    }

    private List getElementAt(Integer element) {
        List tmp = this;
        for(int i = 0; i < element; i++){
            if (tmp.getNext() == null) {  // preventing NPE
                return tmp;
            }
            tmp = tmp.getNext();
        }
        return tmp;
    }

    public void add_nodes()throws IOException {
        Integer number_of_nodes;// store number of nodes
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter number of nodes to add");
        number_of_nodes = Integer.parseInt(br.readLine());
        List ptr = this;
        for(int i = 1 ; i < number_of_nodes ; i++)
        {
            List temp = new List();
            System.out.println("Enter the next data");
            temp.setData(Integer.parseInt(br.readLine()));
            ptr.setNext(temp);
            ptr = ptr.getNext();
        }
    }

    /**
    * Function used to cut n-th element from list
    *
    * @param element - 0 means first element
    */
    public void delete(Integer element){
        List tmp = this.getElementAt(element);
        if (tmp.getNext() == null) {
            return;                // preventing NPE
        }
        tmp.setNext( tmp.getNext().getNext() ); //cutting
    }

    public void insertmid(Integer position, Integer data){
        List tmp = this.getElementAt(position);
        List element = new List(data, tmp.getNext());
        tmp.setNext(element);

    }

    public void rewind(){
        List tmp = this;
        List result = new List(this);
        result.setNext(null);
        while(tmp.getNext() != null) { 
            tmp = tmp.getNext();
            List current = new List(tmp);
            current.setNext(result);
            result = current;
        }
        this.setData(result.getData());
        this.setNext(result.getNext());
    }


    void display()
    {
        List tmp = this;
        while(tmp != null) {
            System.out.print( tmp.getData() + "\t");
            tmp = tmp.getNext();
        }
        System.out.println();
    }

    public static void main(String args[])throws IOException
    {
        List list = new List();

        list.add_nodes();
        list.display();
        list.insertmid(4, 2);
        list.display();
        list.delete(3);
        list.display();
        list.rewind();
        list.display();

    }
}

Answer 5

I had written code only for insert a node in the list at the end. you can add a new method(function) to add a node at the beginning and deleting a node from the list according to your requirements.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Node{
private int data;
private Node next;
private Node prev;

Node(Node n){
    this.data=n.data;
    this.next=n.next;
    this.prev=n.prev;
}

Node(int data){
    this.data=data;
    this.next=null;
    this.prev=null;
}
public int getData() {return data;}
public void setData(int data) {this.data = data;}

public Node getNext() {return next;}
public void setNext(Node next) {this.next = next;}

public Node getPrev() {return prev;}
public void setPrev(Node prev) {this.prev = prev;}
}   

class MyLinkedList{
    private Node start;
    private Node end;


    public Node getStart() {
        return start;
    }


    public void setStart(Node start) {
        this.start = start;
    }


    public Node getEnd() {
        return end;
    }


    public void setEnd(Node end) {
        this.end = end;
    }


    public boolean isEmpty(){
        return start==null;
    }

    //data from arguments
    public void addNode(int data) throws NumberFormatException, IOException{

        Node n=new Node(data);
        if(isEmpty()){
            start=end=n;
        }else
            if(start==end){
                start.setNext(n);
                n.setPrev(start);
                end=n;
            }
        else{
            end.setNext(n);
            n.setPrev(end);
            end=n;
        }

    }



    public void reverse() throws NumberFormatException, IOException{
        MyLinkedList revList=new MyLinkedList();
        Node currNode=this.getEnd();

        do{

            revList.addNode(currNode.getData());
            currNode=currNode.getPrev();
        }while(currNode!=null);

        this.start=revList.getStart();
        this.end=revList.getEnd();
    }

    public void traverseFromStart(){
        Node n=start;
        do{

            System.out.print(n.getData()+"-->");
            n=n.getNext();
        }while(n!=null);
        System.out.println();
    }

    public void traverseFromEnd(){
        Node n=end;
        do{

            System.out.print(n.getData()+"-->");
            n=n.getPrev();
        }while(n!=null);
        System.out.println();
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        MyLinkedList list=new MyLinkedList();
        System.out.print("Enter No. of Nodes:");
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        int noOfNodes=Integer.parseInt(in.readLine());

        for(int i=0;i<noOfNodes;i++){
            System.out.print("Enter value of this node:");

            list.addNode(Integer.parseInt(in.readLine()));
        }


        list.traverseFromStart();
        list.traverseFromEnd();
        list.reverse();
        list.traverseFromStart();
        list.traverseFromEnd();

    }
}

Answer 6

To do this, the code iterates over the elements in the list using a for-each loop and concatenates each element to the front of a string variable called output. After the loop is finished, the code prints out the output string.

    public static void reverseList(LinkedList<String> list) {
    String output = "";
    for (String element : list) {
        output = element + " " + output;
    }
    System.out.println(output);
}