Detailed explanation of the use of linked list definitions of Python data structures and algorithms

This article mainly introduces the definition and usage of linked lists in Python data structures and algorithms. It analyzes the definitions, usage methods and related precautions of singly linked lists, circular linked lists, etc. in detail based on specific examples. Friends in need can refer to it. Next

The examples in this article describe the definition and usage of linked lists in Python data structures and algorithms. Share it with everyone for your reference, the details are as follows:

This article will explain to you:

(1) Starting from the definition of linked list nodes, use the class method and object-oriented thinking to create the linked list Design

(2) Boundary conditions that need to be considered when implementing member functions such as insertion and deletion of linked list classes,
prepend (head insertion), pop (head deletion), append (tail insertion), pop_last (Tail deletion)

2.1 Insertion:

Empty linked list
The length of the linked list is 1
Insert to the end

2.2 Delete

Empty linked list
The length of the linked list is 1
Delete the last element

(3) Numerous variations from singly linked list to singly linked list:

Singly linked list with tail node
Cyclic singly linked list
Double linked list

1. Definition of linked list nodes

class LNode:
 def __init__(self, elem, next_=None):
  self.elem = elem
  self.next = next_

2. Implementation of singly linked list

Focus on understanding the implementation of insertion and deletion and the boundary conditions that need to be considered:

class LinkedListUnderflow(ValueError):
 pass
class LList:
 def __init__(self):
  self._head = None
 def is_empty(self):
  return self._head is None
 def prepend(self, elem):
  self._head = LNode(elem, self._head)
 def pop(self):
  if self._head is None:
   raise LinkedListUnderflow('in pop')
  e = self._head.elem
  self._head = self._head.next
  return e
 def append(self, elem):
  if self._head is None:
   self._head = LNode(elem)
   return
  p = self._head
  while p.next is not None:
   p = p.next
  p.next = LNode(elem)
 def pop_last(self):
  if self._head is None:
   raise LinkedListUnderflow('in pop_last')
  p = self._head
  if p.next is None:
   e = p.elem
   self._head = None
   return e
  while p.next.next is not None:
   p = p.next
  e = p.next.elem
  p.next = None
  return e

Simple summary:

(0) The premise of being able to access p.next.next is that p.next is not empty;
(1) Tail insertion, if the linked list is not Empty, what needs to be changed is the pointer of the tail node;
(2) Tail deletion, if the length of the linked list is not empty, what needs to be changed is the pointer of the penultimate node.

Simple transformation of singly linked list: singly linked list with tail node

class LList1(LList):
 def __init__(self):
  LList.__init__(self)
  self._rear = None
 ...

What we only need to rewrite is: Head insertion, tail insertion, tail deletion

def prepend(self, elem):
 if self._head is None:
  self._head = LNode(elem)
  self._rear = self._head
 else:
  self._head = LNode(elem, self._head)
def append(self, elem):
 if self._head is None:
  self._head = LNode(elem)
  self._rear = self._head
 else:
  self._rear.next = LNode(elem)
  self._rear = self._rear.next
def pop_last(self):
 if self._head is None:
  raise LinkedListUnderflow('in pop_last')
 p = self._head
 if p.next is None:
  e = p.elem
  self._head = None
  return e
 while p.next.next is not None:
  p = p.next
 e = p.next.elem
 self._rear = p
 p.next = None
 return e

Variation of singly linked list: cyclic singly linked list

class LCList:
 def __init__(self):
  self._rear = None
 def prepend(self, elem):
  if self._rear is None:
   self._rear = LNode(elem)
   self._rear.next = self._rear
  else:
   self._rear.next = LNode(elem, self._rear.next)
 def append(self, elem):
  self.prepend(elem)
  self_rear = self._rear.next
 def pop(self):
  if self._rear is None:
   raise LinkedListUnderflow('in pop')
  p = self._rear.next
  if p is None:
   self._rear = None
  else:
   self._rear.next = p.next
  return p.elem
 def printall(self):
  if self._rear is None:
   raise ...
  p = self._rear.next
  while True:
   print(p.elem)
   if p is self._rear:
    break
   p = p.next

The above is the detailed content of Detailed explanation of the use of linked list definitions of Python data structures and algorithms. For more information, please follow other related articles on the PHP Chinese website!