python linked list что это
Linked Lists in Python
In this Python tutorial, we will discuss about Linked Lists in Python. Also, we will see these below topics as:
What are linked lists in python?
Create a linked list in python
Now, we can see how to create a linked list in python.
Let’s create a single node, firstly we will make a Node class that holds some data and a pointer next, which will be used to point to the next node in the linked list.
Example:
After writing the above code (create a linked list in python), when you will print “s.data” then the output will appear as “5”. Here, I have created a single node “s = Node(5)” and after print, it will return the data of the node.
You can refer to the below screenshot for create a linked list in python.
Linked list program in python
Example:
After writing the above code (linked list program in python), when you will display the list then the output will appear. Here, the user is asked for the number of elements to add, and using a loop the data will be appended to the linked list. The linked list value will be displayed in the output.
You can refer to below Output:
Traversing a linked list in python
Traversing means going through every single node, singly linked list traverse in forward direction starting with the head of the linked list and ending at the node which has next value as None.
Example:
After writing the above code (traversing a linked list in python), when you will print then the output will appear as “first second third”. Here, we simply print the value of the current data item and also the next data item by assigning the pointers of the next node.
You can refer to the below screenshot for traversing a linked list in python.
Inserting at the beginning of the linked list in Python
Now, we will see how to Insert at the beginning of the linked list.
To insert at the beginning of the linked list, we will add a new node before the head of the given linked list. The newly added node will become the new head of the linked list.
Example:
After writing the above code (inserting at the beginning of the linked list in python), when you will print then the output will appear as “dec jan feb march”. Now, we will call the function that will add at the start of the list and the new node is inserted at the beginning
You can refer to the below screenshot for inserting at the beginning of the linked list.
You can refer to below Output:
Inserting at the end of the linked list in python
The node is being added to the end of the linked list, this involves pointing the next pointer of the last node to the new data node of the linked list. Now, the current last node will become the second last data and the new node become the last node of the linked list.
Example:
After writing the above code (inserting at the end of the linked list in python), when you will print then the output will appear as ” jan feb march april”. Now, we will call the function that will add the new node at the end of the list.
You can refer to the below screenshot for inserting at the end of the linked list in python.
You can refer to below Output:
Deletion in a linked list in python
Let’s see how we can delete a node in linked list.
To delete a node in a linked list, we will find the previous node of the node to be deleted. We will change the next of the previous node and a function is called to remove a node.
Example:
After writing the above code (inserting at the end of the linked list in python), when you will print then the output will appear as ” march feb”. Now, we will call the function that will remove the specified node from the list.
You can refer to the below Output:
You may like the following Python tutorials:
In this Python tutorial, we have learned about the Linked Lists in Python. Also, we covered these below topics:
Entrepreneur, Founder, Author, Blogger, Trainer, and more. Check out my profile.
Связный список на Python: что это такое и как его реализовать
Давайте поговорим немного о связных списках. Вероятно, вы о них слышали. Скажем, на лекциях по структурам данных. И возможно, вы думали, что это как-то сильно заумно. Почему бы не использовать массив? На самом деле связные списки имеют некоторые преимущества перед массивами и простыми списками. Поначалу эта тема может показаться сложной, но не волнуйтесь: мы все разберем.
Если вы представите себе фотографию людей, взявшихся за руки в хороводе, вы получите примерное представление о такой структуре, как связный список. Это некоторое количество отдельных узлов, связанных между собой ссылками, т. е. ссылками на другие узлы. Связные списки бывают двух видов: однонаправленные и двунаправленные (односвязные и двусвязные).
Источник: Medium.com
В односвязных списках каждый узел имеет одну стрелку, указывающую вперед, а в двусвязных узлы имеют еще и стрелки, указывающие назад. Но на собеседованиях в вопросах, касающихся связных списков, чаще всего имеются в виду односвязные. Почему? Их проще реализовать. Да, у вас не будет возможности перемещаться по списку в обратном направлении, но для отслеживания узлов хватит и однонаправленных связей.
Цепочку создают отдельные скрепки плюс тот факт, что они сцеплены между собой. Поэтому вместо создания класса Linked_list мы просто создадим класс Node и позволим отдельным узлам связываться друг с другом.
Вот и все! Вот как выглядит наш класс полностью:
Проверяем наш связный список
Давайте все это проверим. Начнем с создания нового объекта Node. Назовем его ll (две латинские буквы «l» в нижнем регистре как сокращение Linked List). Назначим ему значение 1.
Как нам увидеть, как выглядит наш список? Теоретически, выглядеть он должен следующим образом:
Но нет способа вывести его именно в таком виде. Нам нужно пройти список, выводя каждое значение. Вы же помните, как проходить список? Мы только что это делали. Повторим:
И просто выводим data в каждом узле. Мы начинаем с шага № 1: создаем новую переменную и назначаем ее головным элементом списка.
Далее мы выводим первый узел. Почему мы не начали с цикла while? Цикл while проитерируется только дважды, потому что только у двух узлов есть next (у последнего узла его нет). В информатике это называется ошибкой на единицу (когда нужно сделать что-то Х раз плюс 1). Это можно представить в виде забора. Вы ставите столб, затем секцию забора, и чередуете пару столб + секция столько раз, сколько нужно по длине.
Для начала мы выведем первый узел, а затем запустим цикл while для вывода всех последующих узлов.
Запустив это для нашего предыдущего списка, мы получим в консоли:
Ура! Наш связный список работает.
Зачем уметь создавать связный список на Python?
Зачем вообще может понадобиться создавать собственный связный список на Python? Это хороший вопрос. Использование связных списков имеет некоторые преимущества по сравнению с использованием просто списков Python.
Традиционно вопрос звучит как «чем использование связного списка лучше использования массива». Основная идея в том, что массивы в Java и других ООП-языках имеют фиксированный размер, поэтому для добавления элемента приходится создавать новый массив с размером N + 1 и помещать в него все значения из предыдущего массива. Пространственная и временная сложность этой операции — O(N). А вот добавление элемента в конец связного списка имеет постоянную временную сложность (O(1)).
Списки в Python это не настоящие массивы, а скорее реализация динамического массива, что имеет свои преимущества и недостатки. В Википедии есть таблица со сравнением производительности связных списков, массивов и динамических массивов.
Если вопрос производительности вас не тревожит, тогда да, проще реализовать обычный список Python. Но научиться реализовывать собственный связный список все равно полезно. Это как изучение математики: у нас есть калькуляторы, но основные концепции мы все-таки изучаем.
В сообществе разработчиков постоянно ведутся горячие споры о том, насколько целесообразно давать на технических интервью задания, связанные с алгоритмами и структурами данных. Возможно, в этом и нет никакого смысла, но на собеседовании вас вполне могут попросить реализовать связный список на Python. И теперь вы знаете, как это сделать.
Связанный список Python
Вот некоторые функции списков, основанные на представлении Мартина фон Лёвиса :
где w = sys.stdout.write
Я никогда не использовал односвязный список в Python для каких-либо задач, кроме образовательных.
узел, содержащий грузовой объект и ссылку на связанный список.
Я написал это на днях
Принятый ответ довольно сложен. Вот более стандартный дизайн:
Неизменяемые списки лучше всего представлены двумя кортежами, где None представляет NIL. Чтобы упростить составление таких списков, вы можете использовать эту функцию:
Для работы с такими списками я бы предпочел предоставить полный набор функций LISP (т.е. first, second, nth и т.д.), чем вводить методы.
Вот немного более сложная версия класса связанного списка с интерфейсом, аналогичным типам последовательностей Python (т.е. поддерживает индексацию, нарезку, конкатенацию с произвольными последовательностями и т. Д.). Он должен иметь начало O (1), не копирует данные, если в этом нет необходимости, и может использоваться взаимозаменяемо с кортежами.
Это не будет так эффективно по пространству или времени, как ячейки cons-lisp, поскольку классы python, очевидно, немного тяжелее (вы можете немного улучшить ситуацию с помощью » __slots__ = ‘_head’,’_tail’ «, чтобы уменьшить использование памяти). Однако он будет иметь желаемые рабочие характеристики с большим O.
dllist объекты
Этот объект представляет собой структуру данных двусвязного списка.
first
Первый dllistnode объект в списке. None если список пуст.
Последний dllistnode объект в списке. Нет, если список пуст.
dllist объекты также поддерживают следующие методы:
append(x)
appendleft(x)
appendright(x)
clear()
Удалите все узлы из списка.
extend(iterable)
Добавьте элементы из iterable в правую часть списка.
extendleft(iterable)
Добавить элементы из iterable в левую часть списка.
extendright(iterable)
Добавьте элементы из iterable в правую часть списка.
insert(x[, before])
nodeat(index)
Удалите и верните значение элемента из правой части списка.
popleft()
Удаляет и возвращает значение элемента из левой части списка.
popright()
Удалить и вернуть значение элемента из правой части списка
remove(node)
Удалить node из списка и вернуть элемент, который в нем хранился.
dllistnode объекты
класс llist.dllistnode([value])
dllistnode объекты предоставляют следующие атрибуты:
Следующий узел в списке. Этот атрибут доступен только для чтения.
Предыдущий узел в списке. Этот атрибут доступен только для чтения.
value
Значение, хранящееся в этом узле. Составлено по этой ссылке
продавец
Python Linked Lists
A linked list is one of the most common data structures used in computer science. It is also one of the simplest ones too, and is as well as fundamental to higher level structures like stacks, circular buffers, and queues.
Generally speaking, a list is a collection of single data elements that are connected via references. C programmers know this as pointers. For example, a data element can consist of address data, geographical data, geometric data, routing information, or transaction details. Usually, each element of the linked list has the same data type that is specific to the list.
Figure 1: Single-linked list
Figure 2: Double-linked list
A single-linked list can be traversed from head to tail whereas traversing backwards is not as easy as that. In contrast, a double-linked list allows traversing the nodes in both directions at the same cost, no matter which node you start with. Also, adding and deleting of nodes as well as splitting single-linked lists is done in not more than two steps. In a double-linked list four pointers have to be changed.
The Python language does not contain a pre-defined datatype for linked lists. To cope with this situation we either have to create our own data type, or have to make use of additional Python modules that provide an implementation of such a data type.
In this article we’ll go through the steps to create our own linked list data structure. First we create a corresponding data structure for the node. Second, you will learn how to implement and use both a single-linked list, and finally a double-linked list.
Step 1: Node as a Data Structure
These methods ensure that we can initialize a node properly with our data ( __init__() ), and cover both the data extraction and storage (via the self.data property) as well getting the reference to the connected node (via the self.next property). The method has_value() allows us to compare the node value with the value of a different node.
Listing 1: The ListNode class
Creating a node is as simple as that, and instantiates an object of class ListNode :
Listing 2: Instantiation of nodes
Having done that we have available three instances of the ListNode class. These instances represent three independent nodes that contain the values 15 (integer), 8.2 (float), and «Berlin» (string).
Step 2: Creating a Class for a Single-Linked List
As the second step we define a class named SingleLinkedList that covers the methods needed to manage our list nodes. It contains these methods:
We will go through each of these methods step by step.
Listing 3: The SingleLinkedList class (part one)
Step 3: Adding Nodes
In case the list is (still) empty the new node becomes the head of the list. If a node is already in the list, then the value of tail is adjusted accordingly.
Listing 4: The SingleLinkedList class (part two)
The list_length() method counts the nodes, and returns the length of the list. To get from one node to the next in the list the node property self.next comes into play, and returns the link to the next node. Counting the nodes is done in a while loop as long as we do not reach the end of the list, which is represented by a None link to the next node.
Listing 5: The SingleLinkedList class (part three)
Listing 6: The SingleLinkedList class (part four)
Listing 7: Creation of nodes and list output
The output is as follows, and shows how the list grows:
Listing 8: Adding nodes to the list
Step 4: Searching the List
Free eBook: Git Essentials
Check out our hands-on, practical guide to learning Git, with best-practices, industry-accepted standards, and included cheat sheet. Stop Googling Git commands and actually learn it!
Listing 9: The search method unordered_search()
Step 5: Removing an Item from the List
Listing 10: Removing a node by node number
Step 6: Creating a Double-Linked List
To create a double-linked list it feels natural just to extend the ListNode class by creating an additional reference to the previous node. This affects the methods for adding, removing, and sorting nodes. As shown in Listing 11, a new property named previous has been added to store the reference pointer to the previous node in the list. We’ll change our methods to use this property for tracking and traversing nodes as well.
Listing 11: Extended list node class
Now we are able to define a double-linked list as follows:
Listing 12: A DoubleLinkedList class
As described earlier, adding nodes requires a bit more action. Listing 13 shows how to implement that:
Listing 13: Adding nodes in a double-linked list
Removing an item from the list similar costs have to be taken into account. Listing 14 shows how to do that:
Listing 14: Removing an item from a double-linked list
Listing 15 shows how to use the class in a Python program.
Listing 15: Building a double-linked list
As you can see, we can use the class exactly as before when it was just a single-linked list. The only change is the internal data structure.
Step 7: Creating Double-Linked Lists with deque
Since other engineers have faced the same issue, we can simplify things for ourselves and use one of the few existing implementations available. In Python, we can use the deque object from the collections module. According to the module documentation:
Deques are a generalization of stacks and queues (the name is pronounced «deck» and is short for «double-ended queue»). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.
For example, this object contains the following methods:
The underlying data structure of deque is a Python list which is double-linked. The first list node has the index 0. Using deque leads to a significant simplification of the ListNode class. The only thing we keep is the class variable data to store the node value. Listing 16 is as follows:
Listing 16: ListNode class with deque (simplified)
The definition of nodes does not change, and is similar to Listing 2. With this knowledge in mind we create a list of nodes as follows:
Listing 17: Creating a List with deque
Adding an item at the beginning of the list works with the append_left() method as Listing 18 shows:
Listing 18: Adding an element at the beginning of a list
Similarly, append() adds a node at the end of the list as Listing 19 shows:
Listing 19: Adding an element at the end of the list
Conclusion
For further reading and alternative implementations you may have a look here:
Acknowledgements
The author would like to thank Gerold Rupprecht and Mandy Neumeyer for their support, and comments while preparing this article.
Linked List in Python
Author: Aditya Raj
Last Updated: April 27, 2021
Linked list is a data structure which contains data objects which are connected by link. Each linked list consists of nodes which have a data field and a reference to the next node in the linked list. In this article, we will study the underlying concept behind linked list and will implement it in python.
What is a node in a linked list?
A node is an object which has a data field and a pointer to another node in the linked list. A simple structure of a node can be shown in the following figure.
Node of a linked list in python
We can implement the above object using a class Node having two fields namely data and next as follows.
A linked list consists of many such nodes. There is a head pointer in the linked list which points to the first node in the linked list or None when the linked list is empty. The following figure depicts a linked list having three nodes.
Linked list in python
We can see that the next field of the last node points to None and the reference Head points to the first Node. An empty linked list will be a linked list having its head pointer pointing to None. An empty linked list can be created in python as follows.
Inserting an element to a linked list
We can insert an element in a linked list at the first position, in the last position on anywhere in between.
To insert an element in a linked list at the beginning, we will first create a node and with the given data and assign its next reference to the first node i.e where the head is pointing. Then we point the head reference to the new node.To perform this operation, we implement the method insertAtBeginning as follows.
To insert an element in a linked list at the end, we just have to find the node where the next element refers to None i.e. the last node. Then we create a new node with the given data and point the next element of the last node to the newly created node. To perform this operation, we implement the method insertAtEnd as follows.
To insert an element at any other given position, we can count the nodes till we reach that position and then we point the next element of the new node to the next node of the current node and the next reference of the current node to the new node. This can be implemented using the insertAtGivenPosition method as follows.
Traversing a linked list
To traverse a linked list in python, we will start from the head, print the data and move to the next node until we reach None i.e. end of the linked list. The following traverse() method implements the program to traverse a linked list in python.
Deleting a node
We can delete a node either from the start or end or in between two nodes of a linked list.
To delete the first node of a linked list, we will first check if the head of the linked list is pointing to None, if yes then we will raise an exception using python try except with a message that the linked list is empty. Otherwise, we will delete the current node referred by head and move the head pointer to the next node. This can be implemented as follows.
To delete the last node of the linked list, we will traverse each node in the linked list and check if the next pointer of the next node of current node points to None,if yes then the next node of current node is the last node and it will get deleted. This can be implemented as follows.
To delete a node in between the linked list, at every node we will check if the position of next node is the node to be deleted, if yes, we will delete the next node and assign the next reference to the next node of the node being deleted. This can be done as follows.
Following is the working python code for implementation of linked list in python.
Conclusion
In this article, we have studied about linked list and implemented it in python. You may have observed how linked lists are different from inbuilt data structures like python dictionary, list and set e.t.c. Please copy the working code and do experiments with it to gain more insight. Stay tuned for more informative articles.
Recommended Python Training
Course: Python 3 For Beginners
Over 15 hours of video content with guided instruction for beginners. Learn how to create real world applications and master the basics.