A linked list is a data structure in which objects are arranged in linear order. The linear order of the array is determined by the array subscript. However, unlike the array, the order of the linked list is determined by the pointers in each object. Linked list provides a simple and flexible representation method for dynamic sets, and can support Algorithm design and analysis - stack and queue All actions listed in.

As shown in the following figure, a two-way linked list L L Each element of L is an object, and each object has a keyword k e y key key and two pointers: n e x t next next and p r e v prev prev. The object can also contain other auxiliary data (or satellite data) x x x is an element of the linked list, then x . n e r t x.nert x.nert points to its successor elements in the linked list, x . p r e v x.prev x.prev points to its precursor element. If x . p r e v = N I L x.prev=NIL x.prev=NIL, then the element x x x has no precursor, so it is the first element of the linked list, that is, the head of the linked list. If x . n e r t = N I L x.nert=NIL x.nert=NIL, then the element x x x has no successor, so it is the last element of the linked list, that is, the tail of the linked list. attribute L . h e a d L.head 50. Head points to the first element of the linked list. If L . h e a d = N I L L.head=NIL 50. Head = nil, the linked list is empty.

Linked lists can take many forms. It can be single linked or double linked, sorted or unordered, cyclic or acyclic. If a linked list is single linked, omit the in each element p r e v prev prev pointer.

class Node(object):
    """Node of bidirectional linked list"""

    def __init__(self, item):
        # item stores data elements
        self.item = item
        # Next indicates the identity of the next node
        self.next = None
        # prev points to the previous node
        self.prev = None

If the linked list is sorted, the linear order of the linked list is consistent with that of the keywords in the linked list elements; Accordingly, the smallest element is the header element, and the largest element is the footer element. If the linked list is not sorted, the elements can appear in any order. In a circular linked list, the header element p r e v prev The prev pointer points to the footer element, and the n e x t next The next pointer points to the header element. We can imagine a circular linked list as a ring composed of various elements. In the rest of this article, we assume that the linked lists we deal with are unordered and double linked.

class BilateralLinkList(object):
    """Bidirectional linked list"""

    def __init__(self):
        self._head = None

    def is_empty(self):
        """Determine whether the linked list is empty"""
        return self._head is None

    def length(self):
        """Linked list length"""
        # The initial pointer points to head
        cur = self._head
        count = 0
        # The pointer to None indicates that the tail is reached
        while cur is not None:
            count += 1
            # Pointer down
            cur = cur.next
        return count

    def items(self):
        """Traversal linked list"""
        # Get head pointer
        cur = self._head
        # Loop traversal
        while cur is not None:
            # Return to generator
            yield cur.item
            # Pointer down
            cur = cur.next

    def add(self, item):
        """Add elements to the head of the linked list"""
        node = Node(item)
        if self.is_empty():
            # The header node pointer is changed to a new node
            self._head = node
        else:
            # The new node pointer points to the original header node
            node.next = self._head
            # The original header prev points to the new node
            self._head.prev = node
            # head points to the new node
            self._head = node

    def append(self, item):
        """Add element to tail"""
        node = Node(item)
        if self.is_empty():  # The linked list has no elements
            # The header node pointer is changed to a new node
            self._head = node
        else:  # Linked list has elements
            # Move to tail
            cur = self._head
            while cur.next is not None:
                cur = cur.next
            # The pointer on the new node points to the old tail
            node.prev = cur
            # The old tail points to the new node
            cur.next = node

    def insert(self, index, item):
        """ Insert element at specified location"""
        if index <= 0:
            self.add(item)
        elif index > self.length() - 1:
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            for i in range(index):
                cur = cur.next
            # The downward pointer of the new node points to the current node
            node.next = cur
            # The up pointer of the new node points to the previous node of the current node
            node.prev = cur.prev
            # The down pointer of the current previous node points to node
            cur.prev.next = node
            # The up pointer of the current node points to the new node
            cur.prev = node

    def remove(self, item):
        """ Delete Vertex  """
        if self.is_empty():
            return
        cur = self._head
        # Delete element at first node
        if cur.item == item:
            # There is only one element
            if cur.next is None:
                self._head = None
                return True
            else:
                # head points to the next node
                self._head = cur.next
                # The up pointer of the next node points to None
                cur.next.prev = None
                return True
        # Move pointer to find element
        while cur.next is not None:
            if cur.item == item:
                # The down pointer of the previous node points to the next node
                cur.prev.next = cur.next
                # The next node up pointer points to the previous node
                cur.next.prev = cur.prev
                return True
            cur = cur.next
        # Delete element in last
        if cur.item == item:
            # The down pointer of the previous node points to None
            cur.prev.next = None
            return True

    def find(self, item):
        """Find whether the element exists"""
        return item in self.items()

	def search(k):
		"""Search for an element key"""
		x = self._head
		while x != None and x != k:
			x = x.next
		return x

The sentry is a dummy object whose function is to simplify the treatment of boundary conditions. For example, suppose in a linked list L L Set objects in L L . n o n e L.none 50. None, the object represents N o n e None None, but also has the same attributes as other objects. For each pair in the linked list code N o n e None All references to None are replaced by references to sentinels L . n o n e L.none 50. Reference to none. As shown in the figure below, this adjustment transforms a conventional two-way linked list into a two-way circular linked list with sentinels L . n o n e L.none 50. None is between the header and footer. attribute L . n o n e . n e x t L.none.next L.none.next points to the header, L . n o n e . p r e v L.none.prev L.none.prev points to the end of the table. Similarly, at the end of the table n e x t next next attribute and header p r e v prev The prev attribute also points to L . n o n e L.none L.none. because L . n o n e . n e x t L.none.next L.none.next points to the header, and we can remove the attribute L . h e a d L.head 50. Head and replace the reference to it with L . n o n e . n e x t L.none.next L.none. Reference to next. The following figure shows that an empty linked list consists of only one sentry, L . n o n e . n e x t L.none.next L.none.next and L . n o n e . p r e v L.none.prev L.none.prev also points to L . n o n e L.none L.none.

Sentinel basically can not reduce the asymptotic time bound of data structure related operations, but can reduce the constant factor. The advantage of using sentinels in loop statements is that they can make the code concise rather than speed up. We should use sentinels with caution. If there are many short linked lists, the extra storage space occupied by their sentinels will cause serious storage waste.