Связанные списки, добавляющие элементы, объединяющие переднюю и заднюю позиции

Question

Я программирую реализацию связанного списка на Java. У меня есть два способа, один, который помещает элементы в передней части списка:

public void addFront(int n){ 
     Node temp=new Node(n); 
     if (llist==null){ 
      first=temp; 
     } 
     else{ 
      llist.next=temp; 
     } 
     llist=temp; 
    } 

Так что, если я добавить элементы в моем списке, как:

l1.addFront(1) 
l1.addFront(2) 
l1.addFront(3) 

Это будет печатать: 1, 2, и 3

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

public void addBack(int n){ 
     Node temp=new Node(n); 
     temp.next=llist; 
     llist=temp; 
     first=temp; 
    } 

Так что, если я добавляю элементы, такие как:

l1.addBack(4) 
l1.addBack(5) 
l1.addBack(6) 

распечатать 6,5,4; все нормально, пока здесь; проблема, когда я хочу сделать следующую строку с последним списком:

l1.addFront(9) 

он только печатает 9 и 6, а остальные цифры заблудились, почему это?

метод печати у меня есть это:

public void print(){ 
     Node curr=first; 
     while(curr!=null){ 
      System.out.println(curr.e); 
      curr=curr.next; 
     } 
    } 

благодаря

Answer 1

Ваши имена методов вызывают немного путаницы, поскольку addBack добавляет к началу списка (и, кажется, сделать это правильно), и вы, очевидно, намерены добавить addFront в конец списка.

Ваш код для addFront на самом деле всегда добавляет новый узел в качестве первого и единственного элемента или как второго элемента, заменяя что-либо там.

Чтобы добавить в конце, вам необходимо пройти список, чтобы найти последний элемент (то есть номер next == null) и установить новый элемент следующим образом, заменив null.

Как и в случае с фрагментами кода, вы планируете использовать llist, чтобы быть последним элементом в списке, вам необходимо поддерживать его в этом состоянии и использовать его вместо перемещения, как описано выше.

Исходя из предположения, что вы действительно хотите, чтобы методы действовали, как описано выше (хотя это кажется обратным), и предположение, что вы хотите сохранить поле llist, удерживая последний элемент, чтобы вам не понадобилось для перехода к списку для добавления в конец, следующий код должен это сделать.

public void addFront(int n){ 
    Node temp=new Node(n); 
    if (llist==null){ 
     first=temp; 
    } 
    else{ 
     llist.next=temp; 
    } 
    llist=temp; 
} 

public void addBack(int n){ 
    Node temp=new Node(n); 
    temp.next=first; 
    first=temp; 
    if (llist == null) 
     llist = first; 
}