Listnode python 3 что это

ListNode[A: A]¶

See Pony collections.List class for usage examples.

Each node contains four fields: two link fields (references to the previous and to the next node in the sequence of nodes), one data field, and the reference to the List in which it resides.

As you would expect functions are provided to create a ListNode, update a ListNode’s contained item, and pop the item from the ListNode.

Additional functions are provided to operate on a ListNode as part of a Linked List. These provide for prepending, appending, removal, and safe traversal in both directions. The Ponylang collections.List class is the correct way to create these. Do not attempt to create a Linked List using only ListNodes.

Example program¶

The functions which are illustrated below are only those which operate on an individual ListNode.

My node has the item value: My Node item My node has the updated item value: My updated Node item Popped the item from the ListNode The ListNode has no (None) item.

Связный список на Python: Коты в коробках

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

Давайте визуализируем сухие определения. Теперь у нас есть коты, которые сидят в коробках. И на каждой коробке написано какая она по порядку и за какой должна стоять.

Что мы будем делать со связным списком:

1. Проверять содержится ли в нем тот или иной элемент;
2. Добавлять узлы в конец;
3. Получать значение узла по индексу;
4. Удалять узлы.

Начать придется с создания двух классов:

В общем случае, у нас получился узел, у которого есть внутри какое-то значение – кот, и ссылка на следующий узел. То есть в классе Box, соответственно, есть кот и ссылка на следующую коробку. Как и у любого списка, у связного тоже есть начало, а именно head. Поскольку изначально там ничего нет, начальному элементу присваивается значение None.

Содержится ли элемент в списке

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

Добавить узел в конец списка

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

Получить узел по индексу

По индексу catIndex мы хотим получить узел-коробку, но поскольку как такового индекса у узлов не предусмотрено, нужно придумать какую-то замену, а именно переменную, которая будет выполнять роль индекса. Эта переменная – это boxIndex. Мы проходимся по всему списку и сверяем «порядковый номер» узла, и при совпадении его с искомым индексом – выдаем результат.

Удалить узел

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

Поиск начинается с головы списка, то есть с первой по счету коробки, и продолжается, пока коробки не закончатся, то есть пока headcat не станет None. Мы проверяем соответствует ли значение, хранящееся в текущем узле, тому, которое мы хотим удалить. Если нет, то мы просто идем дальше. Однако, если соответствует, то мы удаляем его и «перепривязываем» ссылки, то есть мы удаляем N-ую коробку, при этом коробка N-1 теперь ссылается на коробку N+1.

Вот и все, спасибо, что ознакомились с материалом! На самом деле структура LinkedList это не сложно, и важно понимать, как она работает изнутри. Конечно, на Python ее можно было бы реализовать и в lambda-выражениях, это заняло бы гораздо меньше места, однако здесь я преследовала целью объяснить ее строение, и принцип ее работы на Python максимально подробно, а не гнаться за оптимизацией.

Linked Lists in Python

A linked list is a sequential collection of data elements, which are connected together via links. A linked list consists of independent nodes containing any type of data and each node holds a reference or a link to the next node in the list.

The beginning node of a linked list is called the head and the end node is called the tail. All nodes of a linked list are independent and are not stored contagiously in memory.

The above figure shows a linked list with 4 independent nodes. Each node holds the address of the next node and is linked to it. The head node is the first in the list and therefore has no link pointing towards it. The tail node is identified by a “null” value in the link address.

Linked Lists vs Arrays

Linked List	Array
Linked lists have a dynamic size, i.e., they can be changed at runtime.	The size of an array can not be altered at runtime.
Memory is allocated at runtime.	Memory is allocated at the time of compilation.
The linked list uses more memory as each node holds a reference to the next one as well.	For the same number of elements, arrays use less memory.
Accessing elements is more time consuming	Accessing elements is less time consuming
Operations such as insertion/deletion are faster.	Operations such as insertion/deletion are slower.

Types of Linked Lists

There are 4 types of linked lists that can be created in python.

• Singly Linked List
• Circular Singly Linked List
• Doubly Linked List
• Circular Doubly Linked List

Singly Linked List

In a singly linked list, each node holds a value and a reference/link to the next node. It has no link pointing to the previous node. This is the simplest form of a linked list.

Circular Singly Linked List

The circular singly linked list is similar to a singly linked list. The only difference is that the last node holds a reference to the first node of the linked list.

When we reach the last node of the circular singly linked list, we have an option of going back to the first node. This is not possible in the case of a singly linked list.

Doubly Linked List

In a doubly-linked list, each node of the list has two references, one of the previous node and the other of the next node. Thus, each node holds two addresses along with the data value. Since each node has two references, a doubly-linked list allows us to traverse in both directions.

Circular Doubly Linked List

Circular doubly linked lists are similar to doubly linked lists. The only difference is that their first and last nodes are interconnected as well. The head node holds a reference to the tail node and vice versa.

Hence, in a circular doubly linked list we can perform circular traversal by jumping from the first node to the last node or from the last node to the first node.

Creation of Singly Linked List

We can create a singly linked list in python by following the mentioned steps.

• Step 1: First, we create empty head and tail references and initialize both of them with null.
• Step 2: Create a class “node”. The objects of this class hold one variable to store the values of the nodes and another variable to store the reference addresses.
• Step 3: Create a blank node and assign it a value. Set the reference part of this node to null.
• Step 4: Since we have only one element in the linked list so far, we will link both the head and tail to this node by putting in its reference address.

The iterator function

Since the custom-created linked list is not iterable, we have to add an “__iter__” function so as to traverse through the list.

The time complexity for initializing a singly linked list is O(1). The space complexity is O(1) as no additional memory is required to initialize the linked list.

Insertion in Singly Linked List

A node can be inserted in a singly linked list in any one of the following three ways.

• At the beginning of the linked list
• In between the linked list
• At the end of the linked list

Insertion Algorithm

Algorithm to insert a node at the beginning

• Step 1: Create a node and assign a value to it.
• Step 2: Assign the “next” reference of the node as head.
• Step 3: Set the created node as the new head.
• Step 4: Terminate.

Method to insert a node at the beginning

Algorithm to insert a node in between the linked list

• Step 1: Create a node and assign a value to it.
• Step 2: If the previous node doesn’t exist, return an error message and move to step 5.
• Step 3: Assign the “next” reference of the previous node to the “next” reference of the new node.
• Step 4: Set the “next” reference of the previous node to the newly added node.
• Step 5: Terminate.

Method to insert a node in between the linked list

Algorithm to insert a node at the end of the linked list

• Step 1: Create a node and assign a value to it.
• Step 2: If the list is empty, assign new node to head and tail. Move to step 5.
• Step 3: Search for the last node. Once found, set its “next” reference pointing to the new node.
• Step 4: Assign the new node as the tail.
• Step 5: Terminate.

Method to insert a node at the end of the linked list

Time and Space Complexity

In python, instead of iterating over the linked list and reaching the required position, we can directly jump to any point. Therefore, the time complexity of insertion in a singly linked list is O(1).

But, for insertion at the end, the time complexity is O(N) as we need to traverse to the last element. The space complexity is O(1) because it takes a constant space to add a new node.

Traversal in Singly Linked List

A singly linked list can only be traversed in the forward direction from the first element to the last. We get the value of the next data element by simply iterating with the help of the reference address.

Traversing Method

Time and Space Complexity

We need to loop over the linked list to traverse and print every element. The time complexity for traversal is O(N) where ‘N’ is the size of the given linked list. The space complexity is O(1) as no additional memory is required to traverse through a singly linked list.

Searching in a Singly Linked List

To find a node in a given singly linked list, we use the technique of traversal. The only difference, in this case, is that as soon as we find the searched node, we will terminate the loop.

The worst-case scenario for search is when we have the required element at the end of the linked list, in such a case we have to iterate through the entire linked list to find the required element.

Searching Algorithm

• Step 1: If the linked list is empty, return the message and move to step 5.
• Step 2: Iterate over the linked list using the reference address for each node.
• Step 3: Search every node for the given value.
• Step 4: If the element is found, break the loop. If not, return the message “Element not found”.
• Step 5: Terminate.

Searching Method

Time and Space Complexity

The time complexity for searching a given element in the linked list is O(N) as we have to loop over all the nodes and check for the required one. The space complexity is O(1) as no additional memory is required to traverse through a singly linked list and perform a search.

Deletion of node from Singly Linked List

To delete an existing node from a singly linked list, we must know the value that the node holds. For deletion, we first locate the node previous to the given node. Then we point the “next” reference of this node to the one after the node to be deleted.

A node can be deleted from a singly linked list in any one of the following three ways.

• Deleting the first node
• Deleting any given node
• Deleting the last node

Deletion Algorithm

Algorithm to delete a node from the beginning

• Step 1: If the linked list is empty, return a null statement and go to step 5.
• Step 2: If there’s only one element, delete that node and set head and tail to none. Go to step 5.
• Step 3: Set a “temp_node” pointing at head.
• Step 4: Assign head as the next node. Delete the temp node.
• Step 5: Terminate.

Method to delete a node from the beginning

Algorithm to delete a node from between the linked list

• Step 1: If the linked list is empty, return a null statement and go to step 6.
• Step 2: If the value to be deleted is the first node, set head to the next element and remove the first node. Go to step .
• Step 3: Iterate through the linked list and search for the element to be deleted.
• Step 4: Set “prev” as the node before the one to be deleted. Break the loop.
• Step 5: Delete the required node and set “next” reference of “prev” to the node after the deleted one.
• Step 6: Terminate.

Method to delete a node from between the linked list

Algorithm to delete a node from the end

• Step 1: If the linked list is empty, return a null statement and go to step 6.
• Step 2: If there’s only one element, delete that node and set head and tail to none. Go to step 6.
• Step 3: Set a “temp_node” pointing at head. Iterate the linked list till that node points to the second last node of the list.
• Step 4: Assign tail as the temp node. Set temp node to the next node, i.e., last in the list.
• Step 5: Delete the temp_node.
• Step 6: Terminate.

Method to delete a node from the end

Time and Space Complexity

The time complexity for deletion in a singly linked list is O(N) as we have to loop over all the nodes and search for the required one. The space complexity is O(1) as no additional memory is required to delete an element from a singly linked list.

Deletion of entire Singly Linked List

The deletion of an entire singly linked list is quite a simple process. We have to set the two reference nodes “head” and “tail” to none.

Algorithm to delete an entire singly linked list

• Step 1: If the linked list is empty, return an error message and go to step 4.
• Step 2: Delete the “head” node by setting it to none.
• Step 3: Delete the “tail” node by setting it to none.
• Step 4: Terminate.

Method to delete an entire singly linked list

Time and Space Complexity

The time complexity for deletion of an entire singly linked list is O(1) because we are just setting the “head” and “tail” references to none. The space complexity is O(1) as well since there is no additional space required when deleting the references.

Time Complexity of Linked List vs Array

Operations	Array	Linked List
Creation	O(1)	O(1)
Insertion at beginning	O(1)	O(1)
Insertion in between	O(1)	O(1)
Insertion at end	O(1)	O(n)
Searching in Unsorted Data	O(n)	O(n)
Searching in Sorted Data	O(logn)	O(n)
Traversal	O(n)	O(n)
Deletion at beginning	O(1)	O(1)
Deletion in between	O(1)	O(n)/O(1)
Deletion at end	O(1)	O(n)
Deletion of entire linked list/array	O(1)	O(n)/O(1)
Accessing elements	O(1)	O(n)

Interview Questions on Singly Linked List

Write a code to remove duplicate values from an unsorted linked list.

To solve the duplicate value problem, we initialize a set called ‘visited’. It stores every value we encounter while iterating the linked list. If a value already exists in ‘visited’, we can then remove it from the list.

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list to check for any duplicate item. The space complexity is O(N) as well since the ‘visited’ set gets dynamically filled during iteration.

Implement a code to find the Kth to last element in a singly linked list.

To find the Kth to the last element in a linked list, we initialize two pointers. While one pointer iterates to the end of the linked list, the other pointer stops at Kth to the last element.

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list to set the pointers. The space complexity is O(1) as no additional memory is required to assign the references.

Write a code to partition a linked list around a value x. All nodes less than x come before all the nodes greater than or equal to x.

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list to set the partition. The space complexity is O(1) as no additional memory is required.

There are two numbers represented by a linked list, where each node contains a single digit. The digits are placed in reverse order, i.e., the 1’s digit is at the head of the list. Write a function to add the two numbers and returns the sum as a linked list.

The time complexity of this algorithm is O(N) as we need to iterate over the entire linked list. The space complexity is O(n) as we fill up the newly created linked list dynamically.

Determine whether two given singly-linked lists intersect. Return the intersecting node. The intersection is defined based on the node’s reference, not its value. It means that if the nth node of the first linked list is the same as the mth node of the second linked list, then they are intersecting.

The time complexity of this algorithm is O(A + B) where A is the length of the first linked list and B is the length of the second linked list. We need to traverse both lists to find the number of nodes. The space complexity is O(1) as no additional memory is required.

FAQ question

What is a Linked List in Python?

In a linked list, each data element contains a connection to another data element in form of a pointer. Python does not have linked lists in its standard library.

Output

How to Reverse a Linked List in Python?

The iterative method is used in the user-defined reverse() function to reverse the linked list.

Output

How to create a Linked List in Python

A linked list is a data structure made of a chain of node objects. Each node contains a value and a pointer to the next node in the chain.

Output

How to Sort a Linked List in Python?

In the below code, while the node is not null, value is added at the end of the node, Which is given by node = next of node. Then the list of values is sorted.

Output

How to Use the Linked List in a Loop using Python?

To traverse through the Linked list loops can be used. In the below code, a while loop is used to traverse through the linked list.

Output

How to Transform a Linked List to a Normal List in Python?

The list comprehension can be used to convert a linked list into a list.

Output

How to Put Contents from an Array into a Linked List using Python?

We create a node in a linked list for each element of an array arr[] and insert it at the end.

Output

How to Reverse a Linked List Recursively using Python?

The reverse() function is called recursively to reverse the linked list.

Output

How to Pass a Linked List as a Parameter in Python?

The linked list can be passed as a parameter, like any other list by enclosing the elements in [] symbol.

Output

How to Sort a Linked List in Alphabetical Order in Python?

Output

How to Make an Empty Linked List in Python?

The Empty linked list is created by not inserting any elements into the list.

Output

How to Check if an Element is in a Linked List using Python?

The search() user-defined function is used to traverse through the list and search for the elements.

Output

What does Iterator Do in Linked List in Python?

The python has an inbuilt function called iter() which can be used to iterate through the linked list. The next() function will call the next element in the list.

Output

How to make a Doubly Linked List in Python?

The doubly linked list can be traversed in a backward direction thus making insertion and deletion operations easier to perform.

Output

How to Delete a Node in Linked List using Python?

The linked list is traversed through and the element to be deleted is found. Once found the node is removed and the next pointer is made to point to the next following element.

Output

How to Delete the Last Node in the Linked List using Python?

The secondlast node is used to traverse through the linked list till the second last element. Then the last node, which is the next node of the secondlast node is deleted.

Output

How to Loop Through Elements of Linked List in Python?

In the linked list both for loop and while loop can be used to traverse through the list.

Output

How to Convert an Array List into Linked List in Python?

We build a node in a linked list for each element of an array arr[] and insert it at the end.

Output

How to Implement Deque Singly Linked List in Python?

The enqueue and dequeue operations are performed on the singly linked list.

Output

How to Find the Length of a Singly Linked List in Python?

The variable count is incremented till the node becomes null.

Output

How to Insert an Element at a Specific Position in Linked List using Python?

Up to position-1 nodes, traverse the Linked list. Allocate memory and the specified data to the new node once all of the position-1 nodes have been traversed. Point the new node’s next pointer to the current node’s next pointer. Point the current node’s next pointer to the new node.

Output

Why Does a Linked List Return None in Python?

It is possible to reach the end of next without a return statement, any Python function will return None.

Output

How to Find the Smallest Element in the Linked List using Python?

The linked list is traversed until the head is not NULL, and the min variable is set to INT MIN. Then, if the min value is larger than the head value, the head value is assigned to the min node; otherwise, the head point is to the next node. This method should be repeated until the head is not equal to NULL.

Output

How to Concatenate Two Linked Lists in Python?

The dummy node is created, which initially points to some node when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either ‘a’ or ‘b’ and adding it to the tail.

Output

How to Add an Element to the End of a Linked List in Python?

The user-defined push_back() function is used to add elements to the end of the linked list.

Output

How to Append to the Linked List in Python?

The user-defined function append_element() can be used to append elements to the linked list.

Output

How to Add Characters to Linked List in Python?

The characters can be added to the linked list, by passing the character as the node to the append() and push() functions.

Output

How to Move the Elements of the Linked List in Python?

Traverse down the list until you reach the last node. Use two pointers: one for the final node’s address and the other for the second last node’s address. Do the following activities after the loop has ended.

• Set secLast->next = NULL to make the second last the last.
• Use last->next = *head ref as the head .
• Assign the last position as the head ( *head ref = last ).

Output

How to Remove a Node from the Linked List using Python?

Locate the previous node of the to-be-deleted node. Change the preceding node’s next node. To delete a node, the memory of the node is freed.

Output

How to Remove Duplicate Nodes in an Unsorted Linked List using Python?

The user-defined removeduplicate() function that takes a list as an argument and deletes any duplicate node from the list can be used to remove duplicate nodes in an unsorted linked list.

Output

how to merge two unsorted linked lists in python

The dummy node is created, which initially points to some node when the result list is empty. This dummy node is efficient, since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either ‘a’ or ‘b’ and adding it to the tail.

Output

How to Iterate the Linked Lists Backwards in Python?

The head pointer is passed to this method as a node. Check if the next node of a node is Null: If yes, we have reached the end of the linked list. Set the head pointer to this node. If no, pass the next node of the node to the reversetraverse() method.

Output

How to Know if a Linked List has a Loop in Python?

To detect if a linked list has a loop or not hashing approach can be used. In hashing method, The list is traversed and the node address is added to the hash table. If NULL is reached at any time, return false; otherwise, return true if the next of the current nodes points to any of the previously recorded nodes in Hash.

Output

How To Return a Linked List in Python?

Like any other data linked list can also be returned from the function.

Output

How to Index a Linked List in Python?

The Linked List is traversed through and the count variable is used to keep track of the index of the element.

Output

How to Traverse the Linked List in Python?

The while loop can be used to traverse through the linked list.

Output

How to Interleave Two Linked Lists in Python?

Output

How To Make a List that has Some Words Linked Together in Python?

The list has some words can be linked together using List comprehension.

Output

How to Insert an Array in Linked List using Python?

The array is passed as a node to push() and append() function to insert it into a linked list.

Output

How to Implement a Stack using a Linked List in Python?

In stack Implementation using Linked List, a stack contains a top pointer. This is the head of the stack, where items are pushed and popped at the top of the list. The first node’s link field is null, the second node’s link field is the first node’s address, and so on, with the last node’s address in the top pointer.

Output

How to Search a Linked List in Another Linked List in Python?

The user-defined search_list() function can be used to search a linked list in another linked list.

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

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

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

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

Рисунок 1: Односвязный список

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

Рисунок 2: Двусвязный список

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

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

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

Шаг 1: Узел как структура данных

Чтобы иметь структуру данных, с которой мы можем работать, мы определяем узел. Узел реализуется как класс с именем ListNode . Класс содержит определение для создания экземпляра объекта, в данном случае с двумя переменными – data для сохранения значения узла и next для хранения ссылки на следующий узел в списке. Кроме того, узел имеет следующие методы и свойства:

• __init_() : инициализировать узел с данными
• self.data : значение, хранящееся в узле
• self.next : опорный указатель на следующий узел
• has_value() : сравнение значения со значением узла

Эти методы гарантируют, что мы можем правильно инициализировать узел с нашими данными ( __init__ () ) и покрывать как извлечение данных, так и их хранение (через свойство self.data ), а также получение ссылки на подключенный узел (через свойство self.next ). Метод has_value() позволяет сравнить значение узла со значением другого узла.

Листинг 1: Класс ListNode

Создание узла так же просто, как и создание экземпляра объекта класса ListNode :

Листинг 2: Создание экземпляров узлов

Сделав это, мы имеем в наличии три экземпляра класса ListNode . Эти экземпляры представляют собой три независимых узла, которые содержат значения 15 (целое число), 8.2 (поплавок) и “Берлин” (строка).

Шаг 2: Создание класса для односвязного списка

В качестве второго шага мы определяем класс с именем Single Linked List , который охватывает методы, необходимые для управления узлами списка. Он содержит эти методы:

• __init__() : инициировать объект
• list_length() : возвращает количество узлов
• output_list() : выводит значения узлов
• add_list_item() : добавить узел в конец списка
• unordered_search() : поиск в списке узлов с заданным значением
• remove_list_item_by_id() : удалить узел в соответствии с его идентификатором

Мы рассмотрим каждый из этих методов шаг за шагом.

Метод __init__() определяет две внутренние переменные класса с именами head и tail . Они представляют собой начальный и конечный узлы списка. Изначально и head , и tail имеют значение None до тех пор, пока список пуст.

Листинг 3: Класс Single Linked List (часть первая)

Шаг 3: Добавление узлов

Добавление элементов в список осуществляется через add_list_item() . Этот метод требует узла в качестве дополнительного параметра. Чтобы убедиться, что это правильный узел (экземпляр класса ListNode ), параметр сначала проверяется с помощью встроенной функции Python isinstance() . В случае успеха узел будет добавлен в конец списка. Если item не является ListNode , то он создается.

В случае, если список (все еще) пуст, новый узел становится главой списка. Если узел уже находится в списке, то значение tail корректируется соответствующим образом.

Листинг 4: Класс Single Linked List (часть вторая)

Метод list_length() подсчитывает узлы и возвращает длину списка. Чтобы перейти от одного узла к следующему в списке, в игру вступает свойство узла self.next и возвращает ссылку на следующий узел. Подсчет узлов выполняется в цикле while до тех пор, пока мы не достигнем конца списка, который представлен ссылкой None на следующий узел.

Листинг 5: Класс Единого связанного списка (часть третья)

Метод output_list() выводит значения узлов с помощью свойства node data . Опять же, для перехода от одного узла к другому используется ссылка, предоставляемая через свойство next .

Листинг 6: Класс Single Linked List (часть четвертая)

На основе класса SingleLinkedList мы можем создать правильный список с именем track и играть с его методами , как уже описано выше в Listings 3-6 . Поэтому мы создаем четыре узла списка, оцениваем их в цикле for и выводим содержимое списка. Листинг 7 показывает, как это запрограммировать, а Листинг 8 показывает выходные данные.

Листинг 7: Создание узлов и вывод списка

Вывод выглядит следующим образом и показывает, как растет список:

Листинг 8: Добавление узлов в список

Шаг 4: Поиск по списку

Поиск по всему списку осуществляется с помощью метода unordered_search() . Для поиска значения требуется дополнительный параметр. Глава списка-это отправная точка.

Во время поиска мы подсчитываем узлы. Чтобы указать совпадение, мы используем соответствующий номер узла. Метод unordered_search() возвращает список номеров узлов, представляющих совпадения. Например, и первый, и четвертый узел содержат значение 15. Поиск 15 результатов в списке с двумя элементами: [1, 4] .

Листинг 9: Метод поиска unordered_search()

Шаг 5: Удаление элемента из списка

Удаление узла из списка требует корректировки только одной ссылки – та, которая указывает на удаляемый узел, теперь должна указывать на следующий. Эта ссылка хранится удаляемым узлом и должна быть заменена. В фоновом режиме сборщик мусора Python заботится о несвязанных объектах и приводит их в порядок.

Следующий метод называется remove_list_item_by_id() . В качестве параметра он ссылается на номер узла, аналогичный значению, возвращаемому функцией unordered_search() .

Листинг 10: Удаление узла по номеру узла

Шаг 6: Создание Двусвязного списка

Чтобы создать двусвязный список, естественно просто расширить класс ListNode , создав дополнительную ссылку на предыдущий узел. Это влияет на методы добавления, удаления и сортировки узлов. Как показано в Листинге 11 , для хранения ссылочного указателя на предыдущий узел в списке было добавлено новое свойство с именем previous . Мы изменим наши методы, чтобы использовать это свойство также для отслеживания и обхода узлов.

Листинг 11: Класс узлов расширенного списка

Теперь мы можем определить двусвязный список следующим образом:

Листинг 12: Класс Двойного Связанного списка

Как было описано ранее, добавление узлов требует немного больше действий. Листинг 13 показывает, как это реализовать:

Листинг 13: Добавление узлов в двусвязный список

При удалении элемента из списка необходимо учитывать аналогичные затраты. Листинг 14 показывает, как это сделать:

Листинг 14: Удаление элемента из двусвязного списка

В листинге 15 показано, как использовать класс в программе Python.

Листинг 15: Построение двусвязного списка

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

Шаг 7: Создание Двусвязных списков с помощью deque

Поскольку другие инженеры столкнулись с той же проблемой, мы можем упростить вещи для себя и использовать одну из немногих существующих реализаций. В Python мы можем использовать объект deque из модуля collections . Согласно документации модуля:

Деки-это обобщение стеков и очередей (название произносится как “колода” и является сокращением от “двусторонняя очередь”). Deques поддерживают потокобезопасные, эффективные с точки зрения памяти приложения и всплывающие окна с обеих сторон deque с примерно одинаковой производительностью O(1) в любом направлении.

Например, этот объект содержит следующие методы:

• append() : добавить элемент в правую часть списка (конец)
• append_left() : добавить элемент в левую часть списка (head)
• clear() : удалить все элементы из списка
• count() : подсчет количества элементов с определенным значением
• count() : подсчет количества элементов с определенным значением
• count() : подсчет количества элементов с определенным значением
• pop() : удаление элемента из правой части списка (конец)
• pop left() : удаление элемента из левой части списка (head)
• remove() : удаление элемента из списка
• reverse() : перевернуть список

Базовая структура данных deque представляет собой список Python, который является двусвязным. Первый узел списка имеет индекс 0. Использование deque приводит к значительному упрощению класса ListNode . Единственное, что мы сохраняем, – это переменная класса data для хранения значения узла. Листинг 16 выглядит следующим образом:

Листинг 16: Класс ListNode с deque (упрощенный)

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

Листинг 17: Создание списка с помощью deque

Добавление элемента в начало списка работает с помощью метода append_left() как показано в листинге 18 :

Листинг 18: Добавление элемента в начало списка

Аналогично, append() добавляет узел в конец списка, как показано в Листинге 19 :

Листинг 19: Добавление элемента в конец списка

Вывод

Связанные списки как структуры данных просты в реализации и обеспечивают большую гибкость использования. Это делается с помощью нескольких строк кода. В качестве улучшения вы можете добавить счетчик узлов – переменную класса, которая просто содержит количество узлов в списке. Это уменьшает определение длины списка до одной операции с O(1), и вам не нужно проходить весь список.

Для дальнейшего чтения и альтернативных реализаций вы можете посмотреть здесь:

list – Типы данных связанного списка для Python ( https://pythonhosted.org/llist/ )

Признание

Автор хотел бы поблагодарить Герольда Рупрехта и Мэнди Ноймайер за их поддержку и комментарии при подготовке этой статьи.