Когда на самом деле использовать связанные списки

Мы все узнали в школе или в наших учебных лагерях о различных сложных структурах данных. Связанные списки, хэш-карты, двоичные деревья и деревья поиска, стеки, очереди, монотонные очереди и т.д… Мы все также узнали о том, как писать каждый из них, как перемещаться по узлам, добавлять узлы и удалять узлы. Но что хорошего в знании всего этого, если мы на самом деле не знаем, когда использовать эти структуры данных..

Связанные списки

В качестве краткого резюме давайте вспомним, что такое связанные списки. Связанные списки представляют собой серию “узлов”, содержащих значение, а также указатель на следующий узел в серии. В связанном списке у вас есть доступ к “голове” списка, и все последующие узлы можно найти, просматривая список один за другим. Двусвязный список обладает теми же свойствами, за исключением того, что также сохраняется ссылка на “хвост”, а узлы также имеют ссылку на предыдущий узел, и список можно просматривать в обратном порядке. Связанные списки обычно сравниваются с массивами как аналогичная структура данных, и хотя массивы являются “примитивными” структурами данных, они имеют общие черты со связанными списками.

Сходство

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

Различия

Чтобы действительно заметить различия, вам нужно программировать на более старом, скомпилированном языке, таком как C++, Java или C#, где массивы имеют фиксированную длину.

    String[] array = new String[10]; //initializes new array of strings with length 10
    String fifth = array[4]; //access the fifth element in the array (constant time) 

и так далее, в то время как связанные списки требуют доступа к заголовку, и затем цикл для обхода элементов:

LinkedList linkList = new LinkedList();
 //initializes a new linkList with type string. (no length specified)
 linkList.search(4);

//then inside the linkList class:
public  search(int input){ 
  head = current;
  int counter = 1;
  while(current.next != null){
    if(counter == input){
      return current.value
    }
    else{
      counter++;
      current = current.next;
    } 

Здесь мы ищем 4-й элемент списка ссылок, поэтому нам нужно перебрать первые три значения, чтобы получить четвертое. Поскольку сложность пространства-времени является наихудшим сценарием, поиск значения в связанном списке равен O(n) потому что это зависит от длины связанного списка, а также от индекса, который вы ищете. Поиск в массиве, с другой стороны, представляет собой постоянную временную сложность ( O(1) ), поскольку это прямой поиск в ячейке памяти элемента с определенным индексом.

Варианты использования

Таким образом, рассматривая ключевые различия между массивами и связанными списками, мы можем увидеть преимущества и недостатки каждого из них и начать делать выводы о том, когда использовать каждый из них. Связанные списки используют свою ключевую характеристику, чтобы все было быстро и упорядочено, чтобы действительно сиять. Приложения реального мира чаще всего включают использование в других сложных структурах данных. Хэш-таблицы, графики, стеки, очереди и удаления – все они внутренне используют связанные списки.

  // create stack linked list 
  StackUsingLinkedlist stack = new StackUsingLinkedlist(); 
  // insert Stack value at head of linked list
     stack.push(task1); 
     stack.push(task2); 
     stack.push(task3); 
     stack.push(task4);

  while(!stack.isEmpty()){
    //execute the task at the top of the stack (head of linked list)
    execute(stack.pop());
  }

Вывод

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

Следите за обновлениями на следующей неделе для части 2 практических приложений: когда на самом деле использовать стеки.

Рекомендации:

Рекомендации:

Рекомендации:

Оригинал: “https://dev.to/spencerlindemuth/when-to-actually-use-linked-lists-dcf”