Analysis on realization method of Python bidirectional circular linked list

An example of Python bi-directional circular linked list is presented in this paper. To share for your reference, the details are as follows:

Recently, some friends are working on implementing data structures with python. Encounter 1 problem is the realization of bidirectional loop linked list, change the time that point to always throw a cloud.

I personally implemented an python bidirectional circular list. Attached is the code, I hope to help you.

If you do not know what is a bidirectional circular linked list partner, need to relearn the basics of 1 data structure after oh ~~~

In python, a class Node is used to realize the node of the linked list. The node data has three variables:

prev: Precursor pointer: Used to point to the previous node of the current node next: A successor pointer is used to point to the last node of the current node item: The value used to store the value to be stored on the node

The first node of the current node is called the precursor, and the last node is called the successor.

In the linked list class, we have one variable head that is the header pointer to the list

We hold the head of the linked list head, so we can carry out some column operations on it :(since it is a two-way circular linked list, it is easy to make mistakes when modifying the pointer, I will try my best to say it carefully for your reference)

Judgment is empty: is_empty()

The linked list is empty if the header pointer head does not point otherwise it is not empty

Add elements to the header: add(item)

1 Create 1 new node and the value inside is item.

2 Put into the head:

2.1 If the list is empty, node's next and prev point to themselves, then head points to node

Add elements to the tail: append(item)

1 To create a new node node the value in node is item

2 put into the tail:

2.1 If the list is empty, add add to the header

2.2 Non-empty list:

2.2.1 next points to head

2.2.2 prev of node points to prev of head

2.2.3 head prev element next points to node

2.2.4 The prev point of head is changed to node

2.2.5 head pointing to node replaced the head

Add elements at specified locations: insert( pos , item )

1 Create a new node and the value in node is item

2. Find the right place to insert:

2.1 if pos < = 0 is still small, so perform the headplug method add()

2.2 if pos > = the length of the list, then tail-insert is performed append()

2.3 If pos is in the middle of the list:

2.3.1 Define a temporary variable temp to find the first element at the location to be inserted according to the passed pos

2.3.2 prev is set as temp for node and next for node as next for temp

2.3.3 temp's next points to the node prev instead of node

2.3.4 Change next of temp to node

Get the length of the linked list: length()

1 We set 1 temporary variable temp initially to head and 1 counter count initially to 0

2 Let count add 1 and then temp points to its next element 1 until temp meets None, and temp reaches the last element of the list

In this way, you can count how many nodes 1 has returned

Traversal linked list data: travelji()

Set 1 temporary variable temp to head

2 temp prints its own value to the element each time, and then in the next element pointing to itself, 1 temp equals None to the end of the list

Delete linked list elements: remove( item )

1 Turn on temp temporary variable to initialize head,

2 temp constantly points to its next element, each time pointing to an element, it checks whether the current value is item. If item is found, delete it and return True. If it is not found, it returns False at the end

2.1 Deletion process:

2.1.1 The first element of temp is changed to the last element of temp

2.1.2 The last element of temp is changed to the first element of prev

Query for elements: search()

Set a temporary variable temp starting with head and pointing to the next one, each time checking the value of the first one if the same as item returns the end of True

If temp becomes None then it goes to the tail and it doesn't even go back to False

The code!

# -*- coding:utf-8 -*-
#!python3
# The nodes of the linked list 
class Node(object):
 def __init__(self , item ):
  self.item = item # The node number 
  self.prev = None # Used for pointing forward 1 An element 
  self.next = None # Used to point backwards 1 An element 
# Bidirectional circular linked list 
class DoubleCircleLinkList(object):
 def __init__(self):
  self.__head = None # When initialized the header node is set to null, 
 # Determine if the list is empty, head for None  The list is empty 
 def is_empty(self):
  return self.__head is None
 # The method of adding an element to the header 
 def add(self,item):
  node = Node(item) # new 1 A node node  The value inside is theta item
  #  If the list is empty, then node the next and prev Point to yourself ( Because it's a two-way cycle ) . head Point to the node
  if self.is_empty():
   self.__head = node
   node.next = node
   node.prev = node
  #  Otherwise the list is not empty 
  else:
   node.next = self.__head #node the next Let's call it the present head
   node.prev = self.__head.prev #node the prev  As now head the prev
   self.__head.prev.next = node # now head The former 1 An element of next Set to node
   self.__head.prev = node # now head The precursor of   Instead of node
   self.__head = node # Change the header pointer 
 # Add element methods to the tail 
 def append(self , item):
  # If the current list is empty   Call the header insert method 
  if self.is_empty():
   self.add(item)
  # Otherwise the list is not empty 
  else :
   node = Node(item) # new 1 A node node
   # Because it's a bidirectional circular list, so head the prev It's the end of the list 
   node.next = self.__head #node Under the 1 A set to head 
   node.prev = self.__head.prev #node The precursor of is now the precursor of the head 
   self.__head.prev.next = node # The successor of the head precursor is set as node
   self.__head.prev = node # Head own precursor changed node
 # Get the list length   Number of nodes 
 def length(self):
  # If the list is empty   It returns 0
  if self.is_empty():
   return 0
  # If it's not empty 
  else:
   cur = self.__head # Temporary variable cur Represents the current position   I'm going to initialize it as a header head
   count = 1 # set 1 A counter count . cur Each point to 1 A node, count Is the increase 1  At present cur Point to the head, so count Initialized to 1
   # if cur.next not head , cur Now is not the end 1 Three elements. So count it 1 And again let cur Move backward 1 position 
   while cur.next is not self.__head:
    count += 1
    cur = cur.next
   # Breaking out of the loop means that everything is added up 1 time   return count is 1 How many elements are there 
   return count
 # The ability to traverse linked lists 
 def travel(self):
  # If the current self is empty, it is not traversed 
  if self.is_empty():
   return
  # The list is not empty 
  else :
   cur = self.__head # Temporary variable cur Represents the current location, initialized to the head of the list 
   # As long as cur A successor is not a header cur Not the last 1 Three nodes, we just output the current value and let cur Move backward 1 A node 
   while cur.next is not self.__head:
    print( cur.item,end=" " )
    cur = cur.next
   # when cur Subsequent is head Time to break out of the loop, and finally 1 Five nodes have not yet printed values   Print it out here 
   print( cur.item )
 # The top position inserts the node 
 def insert(self, pos , item ):
  # If the position <=0  The header insert method is called 
  if pos <= 0:
   self.add(item)
  # If the position is last 1 One or more   The tail-insert method is called 
  elif pos > self.length() - 1 :
   self.append(item)
  # Otherwise, the insert position is in the middle of the list 
  else :
   index = 0 # Set the counter to mark how many steps we have taken backwards 
   cur = self.__head #cur Marks the current location 
   # let index Every time the increase 1  . cur Back when index=pos-1 When it comes to cur Before the position to be inserted 1 Three elements, and then stop 
   while index < pos - 1 :
    index += 1
    cur = cur.next
   # Out of the loop, cur Before the position to be inserted 1 Three elements, will node Inserted into the cur The back of the 
   node = Node(item) # new 1 A node 
   node.next = cur.next #node The successor is set as cur In the subsequent 
   node.prev = cur #node Is set as cur
   cur.next.prev = node #cur The precursor of the successor was changed node
   cur.next = node #cur Subsequent to node
 # Delete node operation 
 def remove(self,item):
  # If the list is empty   Direct non-Operation 
  if self.is_empty():
   return
  # The list is not empty 
  else:
   cur = self.__head # Temporary variables mark the location, starting from scratch 
   # If the head is   The element to delete 
   if cur.item == item:
    # If only 1 A node   The list is empty  head Set to None
    if self.length() == 1:
     self.__head = None
    # If you have multiple elements 
    else:
     self.__head = cur.next # Head pointer to cur Under the 1 a 
     cur.next.prev= cur.prev #cur The precursor of the successor was changed cur The precursor of 
     cur.prev.next = cur.next #cur The forerunner's successor is changed cur In the subsequent 
   # Otherwise,   The header node is not the node to be removed   We're going to traverse down 
   else:
    cur = cur.next # the cur Move backward 1 A node 
    # Loop to cur Move backward 1 Until the end of the list, during which time remove the node if you can find it, break out of the loop if you can't find it, 
    while cur is not self.__head:
     # Find the element cur That's what you want to delete 
     if cur.item == item:
      cur.prev.next = cur.next #cur The forerunner of cur In the subsequent 
      cur.next.prev = cur.prev #cur The precursor of the following was changed cur The precursor of 
     cur = cur.next
 # Search for the presence of a node 
 def search(self , item):
  # If the list is empty 1 Decide there is no 
  if self.is_empty():
   return False
  # Otherwise the list is not empty 
  else:
   cur = self.__head # Set up temporary cur From the very beginning 
   # cur Moving backwards and forwards, 1 Up to the tail node 
   while cur.next is not self.__head:
    # Return if found during the period 1 a True  End of run 
    if cur.item == item:
     return True
    cur = cur.next
   #  Jump out of the loop cur It points to the tail element   see 1 Let's see if we're looking for the element   Is it returns True
   if cur.item ==item:
    return True
   # None of the elements   It returns False  Did not find 
   return False
if __name__ == "__main__":
 dlcl = DoubleCircleLinkList()
 print(dlcl.search(7))
 dlcl.travel()
 dlcl.remove(1)
 print(dlcl.length())
 print(dlcl.is_empty())
 dlcl.append(55)
 print(dlcl.search(55))
 dlcl.travel()
 dlcl.remove(55)
 dlcl.travel()
 print(dlcl.length())
 dlcl.add(3)
 print(dlcl.is_empty())
 dlcl.travel()
 dlcl.add(4)
 dlcl.add(5)
 dlcl.append(6)
 dlcl.insert(-10,1)
 dlcl.travel()
 print(dlcl.length())
 dlcl.remove(6)
 dlcl.travel()
 print(dlcl.search(7) )
 dlcl.append(55)
 dlcl.travel()

Operation results:

[

False
0
True
True
55
0
False
3
1 5 4 3 6
5
1 5 4 3
False
1 5 4 3 55

]

A variety of data structures are mainly ideas, different people are not 1 set 1 sample, with a person many times the implementation is not 1 set 1 sample. So the above code for reference only ~

If there is a more concise way, welcome everyone to criticize and correct oh ~

For more information about Python, please refer to Python Data Structure and Algorithm Tutorial, Python Coding Operation Skills Summary, Python Function Operation Skills Summary, Python String Operation Skills Summary and Python Introduction and Advanced Classic Tutorial.

I hope this article has been helpful in Python programming.