Односвязный список/Singly Linked List

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

  1. Последовательные элементы связаны указателем
  2. Последний элемент указывает на null-значение
  3. Может рости в размере
  4. Может быть настолько большим сколько надо (пока не закончится память)
  5. Не тратит лишнюю память

Следующие операции делают односвязный список абстрактной структурой даных:

  1. Вставка элемента в список
  2. Удаление элемента из списка
  3. Удаление списка
  4. Подсчет количества элементов
  5. Прохождение списка
  6. Нахождение n-ой ноды

Ниже показан пример того, как выглядит односвязный список:

Представление односвязного списка

Преимущества списков:

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

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

Недостатки списков:

Существует множество проблем связаных с односвязными списками. Главным недостатком односвязных списков есть доступ к определенному элементу. К примеру, чтобы достать нужный нам элемент массива это займет константное время, что в односвязных списках займет в хутшем случае O(n), тоесть просмотр всех элементов списка. 

Пример представления односвязного списка на Java:

/**
  * Definition for singly-linked list.
  */
public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
         val = x;
         next = null;
     }
}
LikeMe: