Структури на данни, обяснени с примери - свързан списък

Точно както гирляндът се прави с цветя, свързаният списък се състои от възли. Ние наричаме всяко цвете на този венец да бъде възел. И всеки от възела сочи към следващия възел в този списък, както и има данни (тук това е вид цвете).

Видове

Единично свързан списък

Единично свързани списъци съдържат възли, които имат dataполе, както и nextполе, което сочи към следващия възел в последователността. Операциите, които могат да се извършват в единично свързани списъци, са вмъкване, изтриване и обръщане.

 head | | +-----+--+ +-----+--+ +-----+------+ | 1 |o-----> | 2 |o-----> | 3 | NULL | +-----+--+ +-----+--+ +-----+------+

Вътрешната реализация на CPython, кадрите и оценените променливи се съхраняват в стека.

За това трябва да повторим само напред aur, за да получим главата, затова се използва единично свързан списък.

Двойно свързан списък

Двойно свързани списъци съдържат възел, който има dataполе, nextполе и друго поле за връзка, prevсочещо към предишния възел в последователността.

 head | | +------+-----+--+ +--+-----+--+ +-----+------+ | | |o------> | |o------> | | | | NULL | 1 | | 2 | | 3 | NULL | | | | <------o| | <------o| | | +------+-----+--+ +--+-----+--+ +-----+------+

Кешът на браузъра, който ви позволява да натиснете бутона НАЗАД и НАПРЕД. Тук трябва да поддържаме двойно свързан списък, URLsкато поле за данни, за да позволим достъп и в двете посоки. За да отидем на предишния URL, ще използваме prevполе, а за да отидем на следващата страница ще използваме nextполе.

Кръгово свързан списък

Циркулярно свързани списъци е единично свързан списък, в който последният възел, nextполето сочи към първия възел в последователността.

 head | | +-----+--+ +-----+--+ +-----+--+ —> | 1 |o-----> | 2 |o-----> | 3 |o----| +-----+--+ +-----+--+ +-----+--+

Проблем с споделяне на време, решен от операционната система.

В среда за споделяне на време операционната система трябва да поддържа списък на настоящите потребители и трябва последователно да позволява на всеки потребител да използва малка част от времето на процесора, един потребител в даден момент. Операционната система ще избере потребител, ще му позволи да използва малко време на процесора и след това ще премине към следващия потребител.

За това приложение не трябва да има NULL указатели, освен ако няма абсолютно никой, който да иска време на процесора, т.е. списъкът е празен.

Основни операции

Вмъкване

За да добавите нов елемент към списъка.

Вмъкване в началото:

  • Създайте нов възел с дадени данни.
  • Посочете новия възел nextкъм стария head.
  • Посочете headтози нов възел.

Вмъкване в средата / края.

Вмъкване след възел X.

  • Създайте нов възел с дадени данни.
  • Точка нов възел е nextна стария Х next.
  • Точка X nextкъм този нов възел.

Сложност във времето: O (1)

Изтриване

За да изтриете съществуващия елемент от списъка.

Изтриване в началото

  • Вземете възела, посочен headкато Temp.
  • Посочете headкъм Темп next.
  • Свободна памет, използвана от Temp възел.

Изтриване в средата / края.

Изтриване след възел X.

  • Вземете възела, посочен Xкато Temp.
  • Точка Х nextкъм Темп next.
  • Свободна памет, използвана от Temp възел.

Сложност във времето: O (1)

Преминаване

За да пътувате през списъка.

Обхождане

  • Вземете възела, посочен headкато Current.
  • Проверете дали Current не е нула и го покажете.
  • Насочете Current към Current's nextи преминете към горната стъпка.

Сложност във времето: O (n) // Тук n е размерът на списъка с връзки

Изпълнение

C ++ изпълнение на единично свързан списък

// Header files #include  struct node { int data; struct node *next; }; // Head pointer always points to first element of the linked list struct node *head = NULL;

Отпечатване на данни във всеки възел

// Display the list void printList() { struct node *ptr = head; // Start from the beginning while(ptr != NULL) { std::cout 

Insertion at the beginning

// Insert link at the beginning void insertFirst(int data) { // Create a new node struct node *new_node = new struct node; new_node->data = data; // Point it to old head new_node->next = head; // Point head to new node head = new_node; std::cout << "Inserted successfully" << std::endl; }

Deletion at the beginning

// Delete first item void deleteFirst() { // Save reference to head struct node *temp = head; // Point head to head's next head = head->next; // Free memory used by temp temp = NULL: delete temp; std::cout << "Deleted successfully" << std::endl; }

Size

// Find no. of nodes in link list void size() { int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) { length++; } std::cout << "Size of Linked List is " << length << std::endl; }

Searching

// Find node with given data void find(int data){ // Start from the head struct node* current = head; // If list is empty if(head == NULL) { std::cout << "List is empty" next == NULL){ std::cout << "Not Found" 

Deletion after a node

// Delete a node with given data void del(int data){ // Start from the first node struct node* current = head; struct node* previous = NULL; // If list is empty if(head == NULL){ std::cout << "List is empty" next == NULL){ std::cout << "Element not found" next; } else { // Skip the current node previous->next = current->next; } // Free space used by deleted node current = NULL; delete current; std::cout << "Deleted succesfully" << std::endl; }

Python Implementation of Singly Linked List

class Node(object): # Constructor def __init__(self, data=None, next=None): self.data = data self.next = next # Function to get data def get_data(self): return self.data # Function to get next node def get_next(self): return self.next # Function to set next field def set_next(self, new_next): self.next = new_next class LinkedList(object): def __init__(self, head=None): self.head = head

Insertion

 # Function to insert data def insert(self, data): # new_node is a object of class Node new_node = Node(data) new_node.set_next(self.head) self.head = new_node print("Node with data " + str(data) + " is created succesfully")

Size

 # Function to get size def size(self): current = self.head count = 0 while current: count += 1 current = current.get_next() print("Size of link list is " + str(count))

Searching

 # Function to search a data def search(self, data): current = self.head found = False while current and found is False: if current.get_data() == data: found = True else: current = current.get_next() if current is None: print("Node with data " + str(data) + " is not present") else: print("Node with data " + str(data) + " is found")

Deletion after a node

 # Function to delete a node with data def delete(self, data): current = self.head previous = None found = False while current and found is False: if current.get_data() == data: found = True else: previous = current current = current.get_next() if current is None: print("Node with data " + str(data) + " is not in list") elif previous is None: self.head = current.get_next() print("Node with data " + str(data) + " is deleted successfully") else: previous.set_next(current.get_next()) print("Node with data " + str(data) + " is deleted successfully")

Advantages

  1. Linked lists are a dynamic data structure, which can grow and shrink, allocating and deallocating memory while the program is running.
  2. Insertion and deletion of node are easily implemented in a linked list at any position.

Disadvantages

  1. They use more memory than arrays because of the memory used by their pointers (next and prev).
  2. Random access is not possible in linked list. We have to access nodes sequentially.
  3. It’s more complex than array. If a language supports array bound check automatically, Arrays would serve you better.

Note

We have to use free() in C and delete in C++ to free the space used by deleted node, whereas, in Python and Java free space is collected automatically by garbage collector.

Original text