• notice
  • Congratulations on the launch of the Sought Tech site

Python data structure and algorithm (2.4) - doubly linked list

Python data structure and algorithm (2.4)-doubly linked list

    • 0.Learning Objectives
    • 1.Introduction to Doubly Linked Lists
      • 1.1 Introduction to Doubly Linked Lists
      • 1.2 Doubly Linked List Node Class
      • 1.3 Doubly Linked List Advantages and Disadvantages
    • 2.Implementation of Doubly Linked List
      • 2.1 Initialization of Doubly Linked List
      • 2.2 Obtaining the Length of Doubly Linked List
      • 2.3 Read the element at the specified position
      • 2.4 Find the specified element
      • 2.5 Insert a new element at the specified position
      • 2.6 Wash out the element at the specified position
      • 2.7 Other useful operations
    • 3.Application of Doubly Linked List
      • 3.1 Application Example of Doubly Linked List
      • 3.2 Implementing Complex Operations Using Basic Operations of Doubly Linked List
    • Related Links

0.Learning Objectives

The singly linked list has only one index pointing to the immediate successor to represent the logical relationship between nodes, so it is convenient to start from any node to find its successor node, but it is more difficult to find the predecessor node.The doubly linked list is to solve this problem.It uses two indicators to represent the logical relationship between nodes.In the previous section, we have discussed the implementation of the singly linked list and its related operations.In this section, we will focus on the doubly linked list.The implementation of the table and its related operations,
Through the study of this section, you should master the following content:

  • Basic concepts of doubly linked lists and their advantages and disadvantages
  • Implementation of basic operations on doubly linked lists
  • Using the basic operations of doubly linked lists to implement complex algorithms

1.Introduction to Doubly Linked List

1.1 Doubly linked list introduction

A doubly linked list is similar to a singly linked list.It also uses the related concepts of nodes and indicators.It belongs to the chained storage structure of the sequential list.The only difference between a singly linked list and a doubly linked list is the doubly linked list.Two indicators are used to represent the logical relationship between nodes, and an indicator field pointing to its immediate predecessor is added.The linked list formed in this way has two chains in different directions-the predecessor chain and the successor chain, so it is called a two-way chain.A list, or doubly linked list,

1.2 Doubly linked list node class

In a doubly linked list, finding its immediate predecessor node based on a known node can be as convenient as finding its immediate successor node.Like a singly linked list, a doubly linked list can also be divided into a node with a head There are two types of nodes and non-leading nodes.This section only discusses the doubly linked list of the leading node.The node diagram of the doubly linked list is shown below.Each node has two indicators-the indicators that point to the immediate successor next and pointer to immediate predecessor previous:

Doubly linked list node
Implemented in Python Doubly linked list node class is as follows:

class Node:
    def __init__(self, data=None ):
        self.data = data
        self.next = None
        self.previous = None

    def __str__(self):
        return str(self.data)
The

previous variable points to the immediate predecessor node, the next variable holds a reference to the immediate successor node, and the data variable is used for Save data, overload the __str__ method for easy printing of node objects,

1.3 Doubly linked list advantages and disadvantages

The advantage of the doubly linked list is that given a node in the doubly linked list, we can traverse it in both directions and directly access its predecessor node, so that in the operation that needs to find the predecessor, it is not necessary to traverse the entire linked list from the beginning., which greatly facilitates operations such as washing out nodes.
The main disadvantages of the doubly linked list are as follows:
? Each node requires an additional precursor index, which requires more space;
? Insertion or washout of nodes requires more index modification operations,

2.Doubly linked list implementation

Similar to a singly linked list, let's implement a doubly linked list class with a head node, and use the head indicator to mark the beginning of the linked list.If you don't know about single linked lists, you can refer to "Single Linked List Table and its operation and implementation" related introduction,

2.1 Initialization of doubly linked list

Initialization of a doubly linked list establishes an empty singly linked list with a header node, and its table length length is initialized to 0.At this time, there are no element nodes in the linked list, but only one header node.:

class DoublyLinkedList:
    def __init__(self, data=None ):
        self.length = 0
        # Initialize the header node
        head_node = Node()
        self.head = head_node

The time complexity of creating a doubly linked list DoublyLinkedList object is O ( 1 ) O(1) O span>(1),

NOTE:If you remember the inheritance mechanism, we can also make DoublyLinkedList inherit from SinglyLinkedList, can greatly simplify the implementation of doubly linked list,

2.2 Get the length of the doubly linked list

To find the length of the doubly linked list, you only need to overload __len__ and return the value of length from the object, so the time complexity is O ( 1 ) O(1) O span>(1):

 def __len__(self):
        return self.length

2.3 Read the specified position element

The algorithm for reading the element at the specified position in the doubly linked list is exactly the same as that of the singly linked list.You only need to use the subsequent chain to access each node, so the complexity of the operation is also O ( n ) O(n) O span>(n), next we will upload multiple __getitem__ operation implements the operation of reading the element at the specified position in the linked list; at the same time, we want to ensure that the index is within the acceptable index range, otherwise an exception of IndexError will be raised:

 def __getitem__(self, index):
        if index > self.length - 1 or index < 0:
            raise IndexError("DoublyLinkedList assignment index out of range")
        else:
            count = -1
            current = self.head
            while count < index:
                current = current.next
                count += 1
            return current.data

Similarly, we can also implement the operation of modifying the specified position element, only need to load the __setitem__ operation, and its complexity is also O ( n ) O(n) O span>(n):

 def __setitem__(self, index, value):
        if index > self.length - 1 or index < 0:
            raise IndexError("DoublyLinkedList assignment index out of range")
        else:
            count = -1
            current = self.head
            while count < index:
                current = current.next
                count += 1

            current.data = value

2.4 Find the specified element

Same as the singly linked list, when searching for the specified element, it is necessary to set an index current to track the node of the linked list, so that it points to each index in turn along the next field.Each time it points to a node, it is judged whether its value is equal to the specified value value, and if so, the node index is returned; otherwise, the search continues, if there is no such element in the linked list, then Raises a ValueError exception with a time complexity of O ( n ) O(n) O span>(n):

 def locate(self, value):
        count = -1
        current = self.head
        while current != None and current.data != value:
            count += 1
            current = current.next
        if current and current.data == value:
            return count
        else:
            raise ValueError("{} is not in sequential list".format(value))

2.5 Insert a new element at the specified position

There are two different ways to insert a new element at the specified position.One is to find the node current at the position to be inserted, and then insert the node to be inserted before current ; Another method is to find the predecessor node prev of the node to be inserted, and then insert the node to be inserted into prev, the operations of the two methods are slightly different, here Taking the operation of the second method as an example, the specific operation of the first method is left for you to deduce.
Since prev points to the successor node of the position to be inserted, if the insertion position is At the end of the list, prev.next.previous cannot be used due to prev.next=None, and in the middle of the list prev.next.previous=prev, so obviously the operations of inserting into the middle of the linked list and the end of the linked list are different,
(1) The steps to insert a node at the end of the doubly linked list are as follows:

  • traverse the list until the last node, and create a new node;
  • point the previous index of the new node to the last node of the linked list;
  • Update the next indicator of the last node of the original linked list to point to the new node,

Insert a node at the end of the doubly linked list

(2) Inserting a node in the middle of a doubly-linked list is similar to a singly-linked list, but requires more steps to modify the index:

  • First traverse the linked list to the predecessor node prev of the insertion position, and create a new node;
  • next of the new node The index points to the next node where the new node is to be inserted, and the previous index of the new node points to prev;
  • previous points to the new node, the next pointer of the prev node points to the new node,

Insert a node in the middle of the linked list
The algorithm is implemented as follows:

 def insert(self, index, data):
        count = 0
        prev = self.head
        # Judge the legitimacy of the insertion position
        if index > self.length or index < 0 :
            raise IndexError("DoublyLinkedList assignment index out of range")
        else:
            new_node = Node(data)
            while count < index:
                prev = prev.next
                count += 1
            new_node.previous = prev
            self.length += 1
            if prev.next:
                # Insert a node in the middle of the linked list
                new_node.next = prev.next
                prev.next.previous = new_node
                prev.next = new_node
            else:
                # end of chain insertion node
                prev.next = new_node

2.6 Wash out the specified position element

To wash out the specified position element, you only need to find the corresponding position node current.After modifying the indicator, wash out the node.It should be noted that, in addition to the need to add currentnext indicator of the predecessor node of code> points to the successor node of current.If the washed element is not the tail element, it is necessary to add the current The previous indicator of the successor node of> points to the predecessor node of current:

wash out the specified position element
The algorithm is implemented as follows:

 def get_node(self, index):
        """Auxiliary function for returning nodes according to their position"""
        if index > self.length - 1 or index < 0:
            raise IndexError("SinglyLinkedList assignment index out of range")
        count = -1
        current = self.head
        while count < index:
            current = current.next
            count += 1
        return current
    def __delitem__(self, index):
        """wash out the specified position element"""
        if index > self.length - 1 or index < 0:
            raise IndexError("SinglyLinkedList assignment index out of range")
        else:
            current = self.get_node(index)
            if current:
                current.previous.next = current.next
            # If the washed out is not the last node
            if current.next:
                current.next.previous = current.previous
            self.length -= 1
            del current

In the insert and wash operations, the operation position is determined first, and then the insert and wash operations are performed, so the time complexity is O ( n ) O(n) O span>(n),

2.7 Some other useful operations

2.7.1 List element output operation

To convert a doubly linked list to a string for printing, use the str function to call the __str__ method on the object to create a printable string representation:

 def __str__(self):
        s = "["
        current = self.head.next
        count = 0
        while current != None:
            count += 1
            s += str(current)
            current = current.next
            if count < self.length:
                s += '<-->'
        s += "]"
        return s

2.7.2 Wash out specified elements

Slightly different from washing out the specified position element, washing out the specified element requires washing out the first node with the same data element as the given value in the linked list, but the operation of modifying the index is similar, and its time The complexity is also O ( n ) O(n) O span>(n):

 def del_value(self, value):
        current = self.head
        while current:
            if current.data == value:
                current.previous.next = current.next
                if current.next:
                    current.next.previous = current.previous
                self.length -= 1
                del current
                return
            else:
                current = current.next
        raise ValueError("The value provided is not present!")

2.7.3 Append a new element to the end of the linked list

In order to conveniently append new elements at the end of the linked list, you can implement the function append:

 def append(self, data):
        new_node = Node(data)
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
        new_node.previous = current
        self.length += 1

The time complexity of this algorithm is O ( n ) O(n) O span>(n), often at the end of the linked list if needed To append new elements, you can use the added tail index tail to track the last element of the linked list.Using the tail index to append new elements at the end of the linked list can reduce the time complexity to O ( 1 ) O(1) O span>(1),

3.Doubly linked list application

Next, we first test the doubly linked list of the above implementation to verify the validity of the operation, and then use the basic operation of the implementation to implement a more complex algorithm,

3.1 Application example of doubly linked list

First initialize a linked list dllist, and append several elements to it:

dllist = DoublyLinkedList()
# Append element at the end of the list
dllist.append('apple')
dllist.append('banana')
dllist.append('orange')
# Insert element at specified position
dllist.insert(0, 'grape') span>
dllist.insert(4, 'lemon') span>

We can directly print the data elements in the linked list, the length of the linked list and other information:

print('Doubly linked list sllist is:', dllist) 
print('The length of the doubly linked list sllist is:', len(dllist))
print('The 0th element of the doubly linked list sllist is:', dllist[0])
# Modify data element
dllist[0] = 'pear'
del(dllist[3])
print('After modifying the bidirectional linked list sllist data:', dllist)

The output of the above code is as follows:

Doubly linked list dllist is: [grape<-->apple<-->banana<-->orange<--> lemon]
The length of the doubly linked list dllist is: 5
The 0th element of the doubly linked list dllist is: grape
After modifying the doubly linked list dllist data: [pear<-->apple<-->banana<-->lemon]

Next, we will demonstrate adding/rinsing elements at specified positions, and how to find specified elements, etc.:

# Modify data element
dllist[0] = 'pear'
print('After modifying the doubly linked list dllist data:', dllist)
dllist.insert(0, 'watermelon') span>
print('Add watermelon at position 0 after the doubly linked list ddlist data:', dllist)
del(dllist[3])
print('Doubly linked list ddlist data after washing the element at position 3:', dllist)
dllist.append('lemon')
print('Doubly linked list ddlist data after appending the element lemon at the end:', dllist) 
dllist.del_value('lemon')
print('Doubly linked list dllist data after washing the lemon:', dllist) span>
print('watermelon's index in the doubly linked list dllist is:', dllist.locate('orange'))

The output of the above code is as follows:

After modifying the doubly linked list dllist data: [pear<-->apple<-->banana<-->orange<-->lemon]
After adding watermelon at the position 0, the doubly linked list ddlist data: [watermelon<-->pear<-->apple <-->banana<- span>->orange<--> lemon]
Doubly linked list ddlist data after washing out position 3: [watermelon<-->pear<-->apple <-->orange<-->lemon]
Doubly linked list ddlist data after appending element lemon at the end: [watermelon<--> ;pear<-->apple< -->orange<-->lemon<-->lemon] 
Doubly linked list dllist data after washing out the lemon: [watermelon<-->pear<-->apple<-->orange<-->lemon]
The index of watermelon in the doubly linked list dllist is: 3

3.2 Implementing complex operations using basic operations of doubly linked list

[1] Merge two doubly linked lists using the basic operations of doubly linked lists:

def merge(dllist1, dllist2):
    current = dllist1.head
    while current.next:
        current = current.next
    if dllist2.head.next:
        tmp = dllist2.head.next
        current
                  

Tags

Technical otaku

Sought technology together

Related Topic

0 Comments

Leave a Reply

+