Программа для изменения связанного списка в Java

Question

Я написал следующий код, в котором метод rev(list,list) не работает. Пожалуйста, помогите мне определить, что случилось.

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

Первое, что вы должны сделать, это получить себе знакомы с Java Naming Conventions, потому что это сделает ваш чистый код и более понятным. В вашем текущем коде не различаются классы или методы или переменные.

Во-вторых, кажется, что вы едете из C++ фона и не знаю, что Java всегда passes by value

Вот одна вещь, которую вы делаете, что не имеет никакого смысла:

void rev(list lst,list lst1) 
{ 

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

Кодекса ниже практически эквивалентны:

void rev(list lst) 
{ 

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

Теперь, я не буду вдаваться в очистке весь свой код, но я дам вам алгоритм обратного Связанная Список которые вы можете включить в свою программу:

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

Вы можете попробовать это с помощью классов Java Collection:

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

Пожалуйста, пожалуйста следовать стандартным соглашениям по именованию. Это сделает ваш код много легче читать. В частности, имена ссылочных типов (классы и интерфейсы) должны начинаться с заглавных букв (например, List), тогда как имена методов и переменных экземпляра должны начинаться с строчных букв.

Вот некоторые комментарии на ваш нерабочем метод:

void rev(list lst,list lst1) 
{ 

Бессмысленно проходить lst1, если вы сразу же собираетесь выбросить то, что значение было принято, так как вы здесь:

lst1=null; 

Здесь также бессмысленно инициализировать переменную 'ptr', поскольку первое, что вы делаете с ней (в начале цикла), назначает новое значение. Фактически, было бы чище объявить его внутри тела цикла.

list ptr=new list(); 

Следующий цикл выглядит это, наверное, хорошо, но рассмотрит состояние, в котором он покидает объект сначала ссылается lst. Подсказка: lst1 инициализируется null.

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

Теперь рассмотрим, что Java только передать по значению, так что все ссылки передаются этому методу не изменяются с точки зрения заклинателя в.

} 

Если вы все еще не видите это, рассмотрите этот вопрос: какой узел находится во главе списка?

В более общем смысле у вас есть небольшая проблема моделирования, так как ваш класс list пытается сделать двойной долг, представляя не только общий список, но и узел в этом списке. Это может работать, и у него есть свойства, которые могут быть полезны, но также обладают свойствами, которые могут вызвать проблемы. Например, вы не можете представлять пустой список с экземпляром вашего класса. Вы также не можете с пользой обратить вспять список, представленный экземпляром вашего класса, методом, имеющим подпись вашего rev().

Answer 4

Использование класса Java Naming Convention я подготовил и переписал свой код, чтобы работать, как Вы спросили:

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

Я написал код только для вставки узла в списке в конце. вы можете добавить новый метод (функцию) для добавления узла в начале и удаления узла из списка в соответствии с вашими требованиями.

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(); 

    } 
}