Для односвязного списка всегда нужно добавлять новый узел в качестве первого элемента? - PullRequest
Новая
       7

Для односвязного списка всегда нужно добавлять новый узел в качестве первого элемента?

0 голосов
/ 28 апреля 2018

Обычно в односвязном списке всегда ли вы добавляете новый элемент в качестве head.next, другими словами, в качестве первого элемента? Или вы идете до конца списка и добавляете его туда?

Ответы [ 3 ]

0 голосов
/ 28 апреля 2018

Как сказал @munk, возможен любой путь. Однако временная сложность вставки может варьироваться в зависимости от используемой вами структуры. Позвольте мне быть более ясным.

Давайте использовать C lang просто, чтобы сделать это просто. Возможный способ реализации единого связанного списка: 

typedef struct node {
    int foo;
    node_t* next;
} node_t;

typedef struct list {
    node_t* head;
} list_t;

Таким образом, вы сначала создаете структуру node для хранения информации, которую хотите сохранить, а затем объявляете вторую структуру list, которая просто содержит указатель на первый узел списка, то есть head. С этой реализацией:

  • Вставка в начале занимает O(1) время (вам нужно только изменить поле head и внести некоторые изменения с помощью next.
  • Вставка в конце занимает O(n) время, потому что вам придется пройти весь список.



Второй способ реализации единого связанного списка заключается в следующем: 

typedef struct node {
    int foo;
    node_t* next;
} node_t;

typedef struct list {
    node_t* head;
    node_t* tail;
} list_t;

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

0 голосов
/ 29 апреля 2018

Согласно этой лекции из Стэнфордского университета (после 13:00 мин), добавьте прогулки в конец списка и добавьте туда новый узел. Вот скриншот кода (C ++) enter image description here

В лекционных заметках из Калифорнийского университета в Беркли (Java) они добавляют его как первый элемент, но затем они явно вызывают его как insertFront () 

public class SList {
  private SListNode head;             // First node in list.
  private int size;                   // Number of items in list.

  public SList() {                    // Here's how to represent an empty list.
    head = null;
    size = 0;
  }

  public void insertFront(Object item) {
    head = new SListNode(item, head);
    size++;
  }
}

В классе LinkedList в java framework (это двусвязный список), просто добавьте означает добавить в конец списка. Поэтому, если вы добавите 1, то 2, а затем 3, 3 будут последним элементом в списке.

Короче говоря: Если явно не вызывается как addFront (или что-то подобное), добавление в LinkedList означает добавление в качестве последнего элемента.

0 голосов
/ 28 апреля 2018

Возможен любой способ, но вставка спереди обычно предпочтительнее по соображениям производительности.

Вставка нового элемента в качестве заголовка очень быстрая, O (1), потому что вам нужно только создать элемент и указатель на старый заголовок.

Вставка в конце означает обход списка, чтобы найти последний элемент и обновление его указателя на новый элемент. Это O (n).

Вы можете обменять время на хранение, следя за хвостом вашего списка и сделав O (1) вставки до конца. Но тогда у вас есть кое-что более сложное, чем односвязный список.

Обычно квалифицируется

Когда я говорю обычно , я имею в виду созданные вручную односвязные списки, особенно написанные на C, возможно, для какого-то встроенного устройства, где пространство стоит дорого, а дополнительное место для хранения хвоста слишком много

Для языка общего назначения, такого как, например, Java, реализация LinkedList хранит хвост, поэтому обе операции являются O (1). Интересно, что в случае Java абстрактный интерфейс для List определяет только операцию, которая добавляется в список.

Реализация (в псевдо C)

Допустим, у меня есть список, такой как 

struct List {
    int data;
    List *next;
};

Если я хочу вставить в начале, я напишу 

List* insert(List *original_list, int data) {
    List* head = allocate new List(data, original_list);
    return head;
}

Если я хочу добавить, я напишу 

void append(List *original_list, int data) {
    List* new_tail = allocate new List(data, null);
    ptr = original_list
    while(ptr->next != null)
        ptr++
    ptr->next = new_tail;
}
...