Понимание линейного связанного списка

Question

У меня есть некоторые проблемы с пониманием структуры данных линейного связанного списка.Вот как я определяю элемент списка:

class Node{
    Object data;
    Node link;

    public Node(Object pData, Node pLink){
        this.data = pData;
        this.link = pLink;
    }
}

Для простоты мы говорим, что список - это связанные узлы, поэтому нам не нужно определять список классов (принцип рекурсии).

Моя проблема в том, что я действительно запутался в понимании того, как узлы связаны, точнее, в последовательности узлов, когда мы их соединяем.

Node n1 = new Node(new Integer(2), null);
Node n2 = new Node(new Integer(1), n1);

Что такое ссылка?Это предыдущий или следующий элемент?Любые другие предложения, которые помогут мне понять эту структуру данных?

Answer 1

Может быть, этот рисунок поможет вам понять.

(Учтите, что стрелки - это ссылки, а НЕ указатели для Java)

«Список» будет ссылкой на самый первый узел.

Answer 2

link - это ссылка на следующий узел в списке.

Таким образом, вы начнете с первого узла в списке, n1, к которому у вас будет прямая ссылка.Чтобы получить второй узел в списке, вы должны сослаться на n1.link.

. Для итерации по списку вам понадобится какая-то начальная точка, например, n1, а затем повторно указывать link:

Node n = n1;
while (n != null) {
    println(n.data);
    n = n.link;
}

Answer 3

В односвязном списке это «следующий».

Это похоже на Java, даже если вы не пометили его как таковой.Если это правда, рассмотрите использование дженериков:

public class Node<T>
{
    T value;
    Node<T> next;
}

Answer 4

У меня есть два предложения.

Во-первых, насчет «это предыдущий или следующий элемент»: это зависит от вашей структуры данных. Обычно это следующий элемент.

Во-вторых, я бы рекомендовал использовать указатель или ссылку. (И ваш синтаксис C ++ неверен: this является указателем, и оператор new также возвращает указатель. Не уверен, что вы используете C ++, поскольку вы не указали язык.)

Так, например:

class Node {
    Object data;
public:
    Node *next;

    Node (Object pData, Node *pLink) {
        this->data = pData;
        this->next = pLink;
    }
}

Это была бы более правильная структура. Тогда вы можете сделать:

Node *n3 = new Node(new Integer(2), null);
Node *n2 = new Node(new Integer(1), n1);
Node *n1 = new Node(new Integer(3), n2);

или просто

Node *n1 = new Node(new Integer(3), new Node(new Integer(1), new Node(new Integer(2), NULL)));

Тогда вы можете выполнить итерацию по списку следующим образом:

for (Node *current = n1; current != NULL; current = current->next)
{
    // do something with the current element
}

Надеюсь, это поможет!

---

Если вы используете современный язык, в stl C ++ уже есть предварительно созданные структуры связанных списков, в .NET - в System.Collections.Generic, и я уверен, что есть также аналог Java.