Алгоритм LinkedList

Вот реализация алгоритма LinkedList. Алгоритм вставляет узел в beginner, после определенного узла или в конец списка.

package LinkedList;

class LinkedList {

 Node Head;

 class Node {
 int data;
 Node Next;

 public Node(int d) {
 data = d;
 Next = null;
 }
 }

 public void insert(int value) {
 if(Head ==null){
 Head = new Node(value);
 return;
 }
 Node new_node = new Node(value);
 new_node.Next = Head;
 Head = new_node;
 }

 public void display() {
 Node a = Head; 
 while (a != null) {
 System.out.println("value:" + a.data);
 a = a.Next;
 }
 }

 public void insertMiddle(int valueToInsert, Node prev_node) {
 if (Head == null) {
 System.out.println("Cant put value after last node");
 }
 Node new_node = new Node(valueToInsert);
 new_node.Next = prev_node.Next;
 prev_node.Next = new_node;
 }

 public void last(int value){
 Node new_node = new Node(value);
 if(Head == null){
 Head = new Node(value);
 return;
 }
 new_node.Next = null;

 Node last = Head;
 while(last != null){
 last = last.Next ;
 }
 last = new_node;
 return;
 }
}

public class LinkedList_Insertion {
 public static void main(String[] args) {
 // TODO Auto-generated method stub
 LinkedList list = new LinkedList();
 list.insert(8);
 list.insert(20);
 list.insert(0);
 list.insertMiddle(999, list.Head.Next);
 list.display();
 System.out.println("--------------");
 list.last(10000);
 list.display();

 }
}

В приведенном выше коде, используя метод insert:

public void insert(int value) {
 if(Head ==null){
 Head = new Node(value);
 return;
 }
 Node new_node = new Node(value);
 new_node.Next = Head;
 Head = new_node;
 }

почему бы нам не использовать Head.next = new_node;

Аналогично, для метода:

public void last(int value){
 Node new_node = new Node(value);
 if(Head == null){
 Head = new Node(value);
 return;
 }
 new_node.Next = null;

 Node last = Head;
 while(last != null){
 last = last.Next ;
 }
 last = new_node;
 return;
}

почему бы нам не использовать last.next = new_node; ?

Я часто делаю ту же ошибку снова и снова. Если кто-то сможет очистить эту концепцию, я буду благодарен. Ждем вашего ответа!

2 ответа

Ваш второй код кажется неправильным, вы правы, он должен быть последним.next = newNode теперь отвечает на ваш 1-й вопрос, рассматривая 3 nos в связанном списке 100 (head), 200 300. здесь главный узел со значением 100 точек к следующему узлу со значением 200, который должен в свою очередь указывать на узел со значением 300. Теперь предположим, что вы хотите вставить 50 до 100, поэтому, когда вы делаете

Head.next = new_node;

узел со значением 100 делается для указания на следующий узел со значением 50, так что теперь у нас есть 100,50 в связанном списке, а голова - 100, что неверно, поэтому мы делаем

new_node.Next = Head;
 Head = new_node;

в этом случае связанный список становится 50 100 200 300. Таким образом, мы делаем это так.


Тяжелый случай:

Вы можете иметь Head-> node1-> node2-> node3->...-> lastNode

Если вы выполните Head.next = newNode, то node1-> node2-> node3->...-> lastNode будет потерян.

Если у вас есть двусвязный список, вы можете сделать Head.prev = newNode; Head = Head.prev Head.prev = newNode; Head = Head.prev (предыдущее означает предыдущее).

Последний случай:

Этот код:

public void last(int value){
 Node new_node = new Node(value);
 if(Head == null){
 Head = new Node(value);
 return;
 }
 new_node.Next = null;

 Node last = Head;
 while(last != null){
 last = last.Next ;
 }
 last = new_node;
 return;
}

выглядит странно, условие должно быть на самом деле while (last.next != null), но даже тогда вы не вставляете, сначала получаете ссылку на последний элемент в своем списке, затем вы делаете эту ссылку на другой объект, на самом деле это должно быть last.next = newNode, вы правы.

Внедрение связанных списков - это хороший способ понять, как работают ссылки на Java, продолжать практиковать, а также попытаться реализовать двусвязный список.

licensed under cc by-sa 3.0 with attribution.