Hướng dẫn dùng listnode python
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. Show Nội dung chính
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. A single list element is called a node. The nodes are not like arrays which are stored sequentially in memory. Instead, it is likely to find them at different memory segments, which you can find by following the pointers from one node to the next. It is common to mark the end of the list with a NIL element, represented by the Python equivalent Figure 1: Single-linked list There exist two kinds of lists - single and double-linked lists. A node in a single-linked list only points to the next element in the list, whereas a node in a double-linked list points to the previous node, too. The data structure occupies more space because you will need an additional variable to store the further reference. 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 StructureTo have a data structure we can work with, we define a node. A node is implemented as a class named
These methods ensure that we can
initialize a node properly with our data ( Listing 1: The ListNode class
Creating a node is as simple as that, and instantiates an object of class Listing 2: Instantiation of nodes
Having done
that we have available three instances of the Step 2: Creating a Class for a Single-Linked ListAs the second step we define a class named
We will go through each of these methods step by step. The Listing 3: The SingleLinkedList class (part one)
Step 3: Adding NodesAdding items to the list is done via 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 Listing 5: The SingleLinkedList class (part three)
The method Listing 6: The SingleLinkedList class (part four)
Based on the class Listing 7: Creation of nodes and list output
The output is as follows, and shows how the list grows: 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 8: Adding nodes to the list
Step 4: Searching the ListSearching the entire list is done using the method While searching we count the nodes. To indicate a match we use the corresponding node number. The method Listing 9: The search method unordered_search()
Step 5: Removing an Item from the ListRemoving a node from the list requires adjusting just one reference - the one pointing to the node to be removed must now point to the next one. This reference is kept by the node to be removed, and must be replaced. In the background the Python garbage collector takes care of unreferenced objects, and tidies up. The following method is named Listing 10: Removing a node by node number
Step 6: Creating a Double-Linked ListTo create a double-linked list it feels natural just to
extend the 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 dequeSince 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
For example, this object contains the following methods:
The
underlying data structure of 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 Listing 18: Adding an element at the beginning of a list
Similarly, Listing 19: Adding an element at the end of the list
ConclusionLinked lists as data structures are easy to implement, and offer great usage flexibility. It is done with a few lines of code. As an improvement you could add a node counter - a class variable that simply holds the number of nodes in the list. This reduces the determination of the list length to a single operation with O(1), and you do not have to traverse the entire list. For further reading and alternative implementations you may have a look here:
AcknowledgementsThe author would like to thank Gerold Rupprecht and Mandy Neumeyer for their support, and comments while preparing this article. |