Выдает ли единственное число LinkedList вывод в LIFO? - PullRequest
Новая
       0

Выдает ли единственное число LinkedList вывод в LIFO?

1 голос
/ 05 октября 2010

Я работал над списком с единственной привязкой.При создании моего собственного связанного списка я запутался при печати набора узлов в моем настраиваемом связанном списке.

Я хочу знать, отображает ли список с одиночной связью свою коллекцию в виде LIFO, как в стеке?

ниже - мой собственный узел LinkedList, а класс - это класс. Кто-нибудь может мне сказать, печатает ли Singular LinkedList коллекцию в стиле Lifo. 

class MYlinklist
{
    Node header;

    public void Add(int a)
    {
        Node n = new Node();
        n.element = a;
        n.Next = header;
        header = n;
    }

    public void Print()
    {
        Node n = new Node();
        n = header;
        while (n != null)
        {
            Console.WriteLine(n.element.ToString());
            n = n.Next;
        }
    }
}

Ответы [ 2 ]

2 голосов
/ 05 октября 2010

Если вы имеете в виду LinkedList<T>, ответ зависит от того, как вы добавляете новых членов.

Если вы хотите, чтобы связанный список повторялся в LIFO, вы можете сделать этовсегда используя AddFirst для добавления и RemoveFirst для удаления.Это приведет к тому, что он будет вести себя очень похоже на стек.

Хорошая особенность LinkedList<T>, однако, заключается в том, что вы можете добавить куда угодно внутри списка как операцию O (1).

Редактировать:

Если вы хотите, чтобы это был FIFO, вам нужно изменить способ добавления узлов и добавлять их в конец списка, а неначало: 

class MyLinkedList
{
    Node header;
    Node last;

    public void Add(int a) 
    { 
        Node n = new Node(); 
        n.element = a; 
        n.Next = null; // We'll put this at the end...
        if (last == null)
        { 
            header = n;
            last = n;
        }
        else
        {
             last.Next = n;
             last = n;
        }
    } 

    public void Print() 
    { 
        Node n = new Node(); 
        n = header; 
        while (n != null) 
        { 
            Console.WriteLine(n.element.ToString()); 
            n = n.Next; 
        } 
    } 
}
0 голосов
/ 05 октября 2010

Вы добавляете узлы в начале списка (обратите внимание, что вы всегда устанавливаете node.Next для заголовка списка).

Затем вы перебираете заголовок (которыйпоследний вставленный элемент) к хвосту.

Если вы хотите выполнить итерацию в порядке FIFO, вы должны сделать следующее:

  1. Поддерживать ссылку на хвост списка (кака также заголовок, который вы указали в header).
  2. Когда вы добавляете узел, установите tail.Next для нового узла, а затем установите tail, чтобы указать на новый узел.
  3. Ваша итерационная функция может быть неизменной.

Другой вариант - вместо сохранения ссылки на хвост, просто выполнять итерацию по списку каждый раз.Но это связано с необходимостью проходить через элементы n-1 для добавления n-го элемента каждый раз, что означает, что добавление множества элементов является операцией O(n^2).Я бы не рекомендовал делать это, но для начала было бы неплохо, если вы изучаете основы и не уверены в манипулировании хвостовыми ссылками.Однако в рабочем коде у вас всегда должны быть заголовок и хвостовая ссылка для связанных списков.

...