Cara menggunakan LISTNODE pada 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.

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 None.

Figure 1: Single-linked list

There exist two kinds of lists - single and . 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 Structure

To have a data structure we can work with, we define a node. A node is implemented as a class named ListNode. The class contains the definition to create an object instance, in this case, with two variables - data to keep the node value, and next to store the reference to the next node in the list. Furthermore, a node has the following methods and properties:

• class SingleLinkedList:
      def __init__(self):
          "constructor to initiate this object"
          
          self.head = None
          self.tail = None
          return
  

  0: initialize the node with the data

• class SingleLinkedList:
      def __init__(self):
          "constructor to initiate this object"
          
          self.head = None
          self.tail = None
          return
  

  1: the value stored in the node

• class SingleLinkedList:
      def __init__(self):
          "constructor to initiate this object"
          
          self.head = None
          self.tail = None
          return
  

  2: the reference pointer to the next node

• class SingleLinkedList:
      def __init__(self):
          "constructor to initiate this object"
          
          self.head = None
          self.tail = None
          return
  

  3: compare a value with the node value

These methods ensure that we can initialize a node properly with our data (

class SingleLinkedList:
    def __init__(self):
        "constructor to initiate this object"
        
        self.head = None
        self.tail = None
        return

class SingleLinkedList:
    def __init__(self):
        "constructor to initiate this object"
        
        self.head = None
        self.tail = None
        return

class SingleLinkedList:
    def __init__(self):
        "constructor to initiate this object"
        
        self.head = None
        self.tail = None
        return

class SingleLinkedList:
    def __init__(self):
        "constructor to initiate this object"
        
        self.head = None
        self.tail = None
        return

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

node1 = ListNode(15)
node2 = ListNode(8.2)
node3 = ListNode("Berlin")

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

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

• class SingleLinkedList:
      def __init__(self):
          "constructor to initiate this object"
          
          self.head = None
          self.tail = None
          return
  

  4: initiate an object

•     def add_list_item(self, item):
          "add an item at the end of the list"
          
          if not isinstance(item, ListNode):
              item = ListNode(item)
  
          if self.head is None:
              self.head = item
          else:
              self.tail.next = item
  
          self.tail = item
              
          return
  

  2: return the number of nodes

•     def add_list_item(self, item):
          "add an item at the end of the list"
          
          if not isinstance(item, ListNode):
              item = ListNode(item)
  
          if self.head is None:
              self.head = item
          else:
              self.tail.next = item
  
          self.tail = item
              
          return
  

  3: outputs the node values

•     def add_list_item(self, item):
          "add an item at the end of the list"
          
          if not isinstance(item, ListNode):
              item = ListNode(item)
  
          if self.head is None:
              self.head = item
          else:
              self.tail.next = item
  
          self.tail = item
              
          return
  

  4: add a node at the end of the list

•     def add_list_item(self, item):
          "add an item at the end of the list"
          
          if not isinstance(item, ListNode):
              item = ListNode(item)
  
          if self.head is None:
              self.head = item
          else:
              self.tail.next = item
  
          self.tail = item
              
          return
  

  5: search the list for the nodes with a specified value

•     def add_list_item(self, item):
          "add an item at the end of the list"
          
          if not isinstance(item, ListNode):
              item = ListNode(item)
  
          if self.head is None:
              self.head = item
          else:
              self.tail.next = item
  
          self.tail = item
              
          return
  

  6: remove the node according to its id

We will go through each of these methods step by step.

The

class SingleLinkedList:
    def __init__(self):
        "constructor to initiate this object"
        
        self.head = None
        self.tail = None
        return

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

Listing 3: The SingleLinkedList class (part one)

class SingleLinkedList:
    def __init__(self):
        "constructor to initiate this object"
        
        self.head = None
        self.tail = None
        return

Step 3: Adding Nodes

Adding items to the list is done via

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

$ python3 simple-list.py
track length: 0
track length: 1
15
track length: 2
15
8.2
track length: 3
15
8.2
Berlin
track length: 4
15
8.2
Berlin
15

$ python3 simple-list.py
track length: 0
track length: 1
15
track length: 2
15
8.2
track length: 3
15
8.2
Berlin
track length: 4
15
8.2
Berlin
15

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)

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

The

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

class SingleLinkedList:
    def __init__(self):
        "constructor to initiate this object"
        
        self.head = None
        self.tail = None
        return

Listing 5: The SingleLinkedList class (part three)

The method

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

Listing 6: The SingleLinkedList class (part four)

Based on the class

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

    def add_list_item(self, item):
        "add an item at the end of the list"

        if isinstance(item, ListNode):
            if self.head is None:
                self.head = item
                item.previous = None
                item.next = None
                self.tail = item
            else:
                self.tail.next = item
                item.previous = self.tail
                self.tail = item
        
        return

    def add_list_item(self, item):
        "add an item at the end of the list"

        if isinstance(item, ListNode):
            if self.head is None:
                self.head = item
                item.previous = None
                item.next = None
                self.tail = item
            else:
                self.tail.next = item
                item.previous = self.tail
                self.tail = item
        
        return

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

$ python3 simple-list.py
track length: 0
track length: 1
15
track length: 2
15
8.2
track length: 3
15
8.2
Berlin
track length: 4
15
8.2
Berlin
15

Step 4: Searching the List

Searching the entire list is done using the method

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

While searching we count the nodes. To indicate a match we use the corresponding node number. The method

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

    def add_list_item(self, item):
        "add an item at the end of the list"

        if isinstance(item, ListNode):
            if self.head is None:
                self.head = item
                item.previous = None
                item.next = None
                self.tail = item
            else:
                self.tail.next = item
                item.previous = self.tail
                self.tail = item
        
        return

Listing 9: The search method unordered_search()

Step 5: Removing an Item from the List

Removing 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

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

    def add_list_item(self, item):
        "add an item at the end of the list"
        
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item
            
        return

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

track = deque([node1, node2, node3])
print("three items (initial list):")
for item in track:
    print(item.data)

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

    def add_list_item(self, item):
        "add an item at the end of the list"

        if isinstance(item, ListNode):
            if self.head is None:
                self.head = item
                item.previous = None
                item.next = None
                self.tail = item
            else:
                self.tail.next = item
                item.previous = self.tail
                self.tail = item
        
        return

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 object from the

track = deque([node1, node2, node3])
print("three items (initial list):")
for item in track:
    print(item.data)

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:

• track = deque([node1, node2, node3])
  print("three items (initial list):")
  for item in track:
      print(item.data)
  

  5: add an item to the right side of the list (end)

• track = deque([node1, node2, node3])
  print("three items (initial list):")
  for item in track:
      print(item.data)
  

  6: add an item to the left side of the list (head)

• track = deque([node1, node2, node3])
  print("three items (initial list):")
  for item in track:
      print(item.data)
  

  7: remove all items from the list

• track = deque([node1, node2, node3])
  print("three items (initial list):")
  for item in track:
      print(item.data)
  

  8: count the number of items with a certain value

• track = deque([node1, node2, node3])
  print("three items (initial list):")
  for item in track:
      print(item.data)
  

  9: find the first occurrence of a value in the list
• None0: insert an item in the list
• None1: remove an item from the right side of a list (end)
• None2: remove an item from the left side of a list (head)
• None3: remove an item from the list
• None4: reverse the list

The underlying data structure of None5 is a Python list which is double-linked. The first list node has the index 0. Using None5 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

track = deque([node1, node2, node3])
print("three items (initial list):")
for item in track:
    print(item.data)

Adding an item at the beginning of the list works with the

track = deque([node1, node2, node3])
print("three items (initial list):")
for item in track:
    print(item.data)

Listing 18: Adding an element at the beginning of a list

Similarly,

track = deque([node1, node2, node3])
print("three items (initial list):")
for item in track:
    print(item.data)

Listing 19: Adding an element at the end of the list

Conclusion

Linked 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:

Acknowledgements

The author would like to thank Gerold Rupprecht and Mandy Neumeyer for their support, and comments while preparing this article.

Append python buat apa?

Apa yang dimaksud dengan list di python?

Mengapa menggunakan linked list?

Apa itu tipe data python?