Структури даних, пояснені на прикладах - зв’язаний список

Подібно до того, як гірлянду роблять з квітів, пов’язаний список складається з вузлів. Ми називаємо кожну квітку на цій конкретній гірлянді вузлом. І кожен з вузлів вказує на наступний вузол у цьому списку, а також має дані (тут це тип квітки).

Типи

Єдинозв’язаний список

Однопов'язані списки містять вузли, що мають 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 не має значення null, і відобразіть його.
  • Вкажіть струм на струм 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