Односвязный список в структурах данных

Что такое односвязный список?

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

Вот структура узла односвязного списка:

Структура узла в связанном списке
Структура узла в связанном списке

Зачем использовать связанный список вместо массива?

В некоторых случаях лучше использовать связанный список, а не массив. Вот несколько сценариев:

  • Неизвестное количество элементов: Если вы не знаете, сколько элементов вам нужно сохранить во время работы программы, вы можете использовать связанный список. Память выделяется динамически по мере добавления элементов в связанные списки.
  • Произвольный доступ: В сценарии, где вам не нужно использовать произвольный доступ к элементам, вы можете использовать связанный список.
  • Вставка посередине: Вставка в середину массива — сложная задача. Потому что вам нужно сдвинуть другие элементы вправо. Однако связанный список позволяет вам добавлять элемент в любую нужную вам позицию.

Operaции односвязного списка

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

Здесь мы обсудим следующую операцию со связанным списком:

  • Вставка в голову
  • Вставка в хвост
  • Вставка после узла
  • Вставка перед узлом
  • Удалить головной узел
  • Удалить хвостовой узел
  • Найти и удалить узел
  • Обход связанного списка

Вот пример связанного списка с четырьмя узлами.

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

Вставка в начало односвязного списка

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

Для выполнения этой операции нам необходимо соблюсти два важных условия. Они

  1. Если список пуст, то вновь созданный узел будет головным узлом, а следующий головной узел будет иметь значение «NULL».
  2. Если список не пуст, новый узел будет головным узлом, а следующий будет указывать на предыдущий головной узел.

Вот псевдокод для вставки узла в начало связанного списка:

function insertAtHead( head, value ):
	newNode = Node(value)
	if head is NULL:
		head = newNode
		return head
	else: 
		newNode.next = head
		return newNode
Вставка в голову
Вставка в голову

Вставка в конец односвязного списка

Вставка узла в конец связанного списка имеет некоторое сходство с вставкой в ​​голову. Все, что вам нужно сделать, это перейти к конечному узлу или хвостовому узлу. Затем укажите «следующий» узел конечного узла на вновь созданный узел. Если головной узел имеет значение NULL, новый узел будет головным узлом.

Вот шаги:

Шаг 1) Перемещайтесь до тех пор, пока «следующий» узел текущего узла не станет нулевым.

Шаг 2) Создайте новый узел с указанным значением.

Шаг 3) Назначьте новый узел следующим узлом хвостового узла.

Псевдокод для вставки узла в хвост отдельного списка:

function insertAtEnd( head, value ):
	newNode = Node(value)
	if head is NULL:
		head = newNode
		return head
	while head.next is not NULL:
		then head = head.next
	head.next = newNode
	newNode.next = NULL
Вставка в хвост
Вставка в хвост

Вставка после узла в односвязном списке

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

Вот шаги:

Шаг 1) Проходите следующий узел до тех пор, пока значение текущего узла не станет равным искомому элементу.

Шаг 2) Следующий указатель нового узла будет следующим указателем текущего узла.

Шаг 3) Следующий узел текущего узла будет новым узлом.

Вот псевдокод для вставки узла после узла:

function insertAfter( head, value, searchItem ):
	newNode = Node(value)
	while head.value equals searchItem:
		then head = head.next
	newNode.next = head.next.next
	head.next = newNode
Вставка узла после узла в односвязном списке
Вставка узла после узла в односвязном списке

Вставка перед узлом в односвязном списке

Эта функция очень похожа на вставку после узла. Мы должны создать новый узел и перемещаться по связанному списку до тех пор, пока текущий узел не будет соответствовать узлу поиска. После этого мы добавим новый узел в качестве предыдущего узла текущего узла.

Вот шаги:

Шаг 1) Перемещайтесь до тех пор, пока значение следующего узла не станет равным искомому элементу.

Шаг 2) Создайте новый узел и назначьте «следующий» узла следующему узлу текущего узла.

Шаг 3) Назначьте новый узел следующим узлом текущего узла.

Вот псевдокод:

function insertBefore( head, value, searchItem ):
	newNode = Node(value)
	while head.next.value equals searchItem:
		then head = head.next
	newNode.next = head.next.next
	head.next = newNode
Вставка узла перед узлом в односвязном списке
Вставка узла перед узлом в односвязном списке

Удалить заголовок односвязного списка

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

Вот шаги для удаления главы односвязного списка:

Шаг 1) Назначьте следующий узел головного узла в качестве нового головного.

Шаг 2) Освободите память, выделенную предыдущим головным узлом.

Шаг 3) Верните новый головной узел.

Псевдокод удаления головного узла:

function deleteHead( head ):
	temp = head
	head = head.next
	free( temp )
	return head
Удаление главы связанного списка
Удаление главы связанного списка

Удалить хвост односвязного списка

Удаление хвостового узла более похоже на удаление головного узла. Разница в том, что нам нужно перейти к концу связанного списка и удалить его. В односвязном списке узел, следующий за которым имеет значение «NULL», является хвостовым узлом.

Вот шаги для удаления хвостового узла связанного списка:

Шаг 1) Траверс перед хвостовым узлом. Сохраните текущий узел.

Шаг 2) Освободите память следующего узла текущего узла.

Шаг 3) Установите следующий узел текущего узла как NULL.

Вот псевдокод для удаления хвостового узла:

function deleteTail( head ):
	while head.next.next is not NULL:
		head = head.next
	free( head.next )
	head.next = NULL
Удаление хвоста односвязного списка
Удаление хвоста односвязного списка

Найти и удалить узел из односвязного списка

Эта функция имеет две задачи: поиск и удаление. Нам нужно искать до конца односвязных списков. Если мы найдем какой-либо похожий узел, мы удалим его. После этого нам нужно объединить или связать левый и правый узлы удаленного узла. Вот шаги для этого:

Шаг 1) Пройти до конца связанного списка. Проверьте, равен ли текущий узел узлу поиска или нет.

Шаг 2) Если какой-либо узел соответствует, сохраните указатель узла на текущий узел.

Шаг 3) «Следующий» предыдущего узла будет следующим узлом текущего узла.

Шаг 4) Удалить и освободить память текущего узла.

Псевдокод для поиска и удаления узла из односвязного списка:

function searchAndDelete( head, searchItem ):
	while head.next.next is not NULL  and head.next.value is not equals searchItem :
		head = head.next
	head.next = head.next.next
	delete(head.next)
Найдите и удалите узел из односвязного списка
Найдите и удалите узел из односвязного списка.

Обход односвязного списка

Односвязный список имеет функцию перемещения только от головы к хвосту. На предыдущий узел нет указателей; вот почему мы не можем пройти по односвязному списку в обратном порядке. Мы будем проходить каждый узел и печатать значение текущего узла, пока не получим ноль.

Вот шаги:

Шаг 1) Проходим каждый узел, пока не получим значение null в качестве следующего узла.

Шаг 2) Выведите значение текущего узла.

Псевдокод для обхода односвязного списка:

function traverse( head ):
		while head.next is not NULL:
			print the value of the head
			head = head.next

Пример односвязного списка в C++

#include<iostream>
using namespace std;
struct Node{
  int data;
  struct Node *next;
};
void insertAtHead(Node* &head, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  if(head!=NULL){
    newNode->next = head;
  }
  head = newNode;
  cout<<"Added "<<newNode->data<<" at the front"<<endl;
}
void insertEnd(Node* &head, int value){
  if(head==NULL){
    insertAtHead(head,value);
  }
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *temp = head;
  while(temp->next!=NULL){
    temp = temp->next;
  }
  temp->next = newNode;
  cout<<"Added "<<newNode->data<<" at the end"<<endl;
}
void searchAndDelete(Node **headPtr, int searchItem){
  Node *temp = new Node();
  if( (*headPtr)->data == searchItem ){
    temp = *headPtr;
    *headPtr = (*headPtr)->next;
    free(temp);
  }else{
    Node *currentNode = *headPtr;
    while(currentNode->next != NULL){
      if(currentNode->next->data == searchItem){
        temp = currentNode->next;
        currentNode->next = currentNode->next->next;
        free(temp);
      }else{
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
}
void insertAfter(Node * &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next!=NULL &&  head->data!=searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl;
}
void insertBefore(Node * &headPtr, int searchItem, int value){
  Node* newNode = new Node();
  newNode->data = value;
  newNode->next = NULL;
  Node *head = headPtr;
  while(head->next!=NULL &&  head->next->data!=searchItem){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
void traverse(Node *headPointer){  
  Node* tempNode = new Node();
  tempNode = headPointer;
  cout<<"Traversal from head:\t";
  while(tempNode !=NULL){
    cout<<tempNode->data;
    if(tempNode->next)
      cout<<" --> ";
    tempNode = tempNode ->next;
  }
  cout<<endl;
}
int main(){
  Node *head = NULL;
  insertAtHead(head,5);
  insertAtHead(head,6);
  insertAtHead(head,7);
  insertEnd(head,9);
  traverse(head);
  searchAndDelete(&head,6);
  traverse(head);
  insertAfter(head,7,10);
  insertBefore(head,9,11);
  traverse(head);
}

Вывод:

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Traversal from head:    7 →  6 →  5 →  9
Deleted Node    6
Traversal from head:    7 →  5 →  9
Inserted 10 after node  7
Inserted 11 before node 9
Traversal from head:    7 →  10 →  5 →  11 →  9

Пример односвязного списка в Python Программа

class Node:
  def __init__(self,data = None, next = None):
    self.data = data
    self.next = next
class SinglyLinkedList:
  def __init__(self):
    self.head = None 
  def insertAtHead(self, value):
    newNode = Node(data=value)    
    if self.head is not None:
      newNode.next = self.head
    self.head = newNode
    print(f'Added {newNode.data} at the front.')
    return  
  def insertAtEnd(self,value):
    if self.head is None:
      self.insertAtHead(value)
    newNode = Node(value)
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    print(f'Added {newNode.data} at the end.')  
  def searchAndDelete(self,searchItem):
    temp = Node()
    if self.head is searchItem:
      temp = self.head
      self.head = self.head.next
    else:
      currentNode = self.head
      while currentNode.next is not None:
        if currentNode.next.data is searchItem:
          temp = currentNode.next
          currentNode.next = currentNode.next.next
        else:
          currentNode = currentNode.next
    print(f'Deleted node\t{searchItem}')
    return
  def insertAfter(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
    return 
  def insertbefore(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
    return
  def traverse(self):
    temp = self.head
    print("Traversing from head:\t",end="")
    while temp:
      print("{}\t".format(temp.data),end="")
      temp = temp.next
    print()
SinglyLinkedList = SinglyLinkedList()
SinglyLinkedList.insertAtHead(5)
SinglyLinkedList.insertAtHead(6)
SinglyLinkedList.insertAtHead(7)
SinglyLinkedList.insertAtEnd(9)
SinglyLinkedList.traverse()
SinglyLinkedList.searchAndDelete(6)
SinglyLinkedList.traverse()
SinglyLinkedList.insertAfter(7,10)
SinglyLinkedList.insertbefore(9, 11)
SinglyLinkedList.traverse()

Вывод:

Added 5 at the front.
Added 6 at the front.
Added 7 at the front.
Added 9 at the end.
Traversing from head:   7       6       5       9
Deleted node    6
Traversing from head:   7       5       9
Inserted 10 after node  7
Inserted 11 before node 9
Traversing from head:   7       10      5       11      9

Сложность односвязного списка

Существует два вида сложности: временная сложность и пространственная сложность. Наихудшая и средняя временная сложность для односвязного списка одинакова.

Временная сложность в лучшем случае:

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

Временная сложность для среднего случая:

  • Вставка внутри связанного списка займет O(n), если в односвязном списке присутствует «n» элементов.
  • Поиск и удаление также могут занимать O(n), поскольку элемент поиска может присутствовать в хвостовом узле. В этом случае вам придется просмотреть весь список.

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

Односвязный список динамически распределяет память. Если мы хотим сохранить n элементов, будет выделено n единиц памяти. Итак, пространственная сложность равна O(n).