概述
<div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?postid=10336387">
<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">链表
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">链表与栈,队列不一样,它是由一个个节点构成的,每个节点存储着本身的一些信息,也存储着其他一个或多个节点的引用,可以从一个节点找到其他的节点,节点与节点之间就像是有链连在一起一样,这种数据结构就叫做链表
:
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class <span class="hljs-title" style="color: #7285b7;">LinkedList<span class="hljs-params" style="color: #ffc58f;">():
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class</span> <span class="hljs-title" style="color: #7285b7;">Node</span><span class="hljs-params" style="color: #ffc58f;">()</span>:</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self,element,next)</span>:</span>
self.element = element
self.next = next
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
self.head = <span class="hljs-keyword" style="color: #ebbbff;">None</span>
self.size = <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">add_head</span><span class="hljs-params" style="color: #ffc58f;">(self,e)</span>:</span>
new = self.Node(e,self.head)
self.head = new
self.size +=<span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">remove_first</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.size == <span class="hljs-number" style="color: #ffc58f;">0</span>:
<span class="hljs-keyword" style="color: #ebbbff;">raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;">'linkedlist is empty'</span>)
self.head = self.head.next
self.size -= <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class</span> <span class="hljs-title" style="color: #7285b7;">Node</span><span class="hljs-params" style="color: #ffc58f;">()</span>:</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self,element,next)</span>:</span>
self.element = element
self.next = next
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
self.head = <span class="hljs-keyword" style="color: #ebbbff;">None</span>
self.size = <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">add_head</span><span class="hljs-params" style="color: #ffc58f;">(self,e)</span>:</span>
new = self.Node(e,self.head)
self.head = new
self.size +=<span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">remove_first</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.size == <span class="hljs-number" style="color: #ffc58f;">0</span>:
<span class="hljs-keyword" style="color: #ebbbff;">raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;">'linkedlist is empty'</span>)
self.head = self.head.next
self.size -= <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class <span class="hljs-title" style="color: #7285b7;">LinkedList<span class="hljs-params" style="color: #ffc58f;">():
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class <span class="hljs-title" style="color: #7285b7;">LinkedList<span class="hljs-params" style="color: #ffc58f;">():
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class</span> <span class="hljs-title" style="color: #7285b7;">Node</span><span class="hljs-params" style="color: #ffc58f;">()</span>:</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self,element,next)</span>:</span>
self.element = element
self.next = next
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
self.head = <span class="hljs-keyword" style="color: #ebbbff;">None</span>
self.size = <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">add_head</span><span class="hljs-params" style="color: #ffc58f;">(self,e)</span>:</span>
new = self.Node(e,self.head)
self.head = new
self.size +=<span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">remove_first</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.size == <span class="hljs-number" style="color: #ffc58f;">0</span>:
<span class="hljs-keyword" style="color: #ebbbff;">raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;">'linkedlist is empty'</span>)
self.head = self.head.next
self.size -= <span class="hljs-number" style="color: #ffc58f;">1</span>
:
<span class="hljs-string" style="color: #d1f1a9;">"""
使用循环链表实现的队列
"""</span>
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class</span> <span class="hljs-title" style="color: #7285b7;">Node</span><span class="hljs-params" style="color: #ffc58f;">()</span>:</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self,next)</span>:</span>
self.element = element
self.next = next
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
self.tail = <span class="hljs-keyword" style="color: #ebbbff;">None</span>
self.size = <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">__len__</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">is_empty</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size == <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">first</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.is_empty():
<span class="hljs-keyword" style="color: #ebbbff;">raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;">'Queue is empty'</span>)
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.tail.next.element
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">dequeue</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.is_empty():
<span class="hljs-keyword" style="color: #ebbbff;">raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;">'Queue is empty'</span>)
old_head = self.tail.next
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.size == <span class="hljs-number" style="color: #ffc58f;">1</span>:
self.tail = <span class="hljs-keyword" style="color: #ebbbff;">None</span>
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
self.tail.next = old_head.next
self.size -= <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> old_head.element
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">enqueue</span><span class="hljs-params" style="color: #ffc58f;">(self,<span class="hljs-keyword" style="color: #ebbbff;">None</span>)
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.is_empty():
new.next = new
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
new.next = self.tail.next
self.tail.next = new
self.tail = new
self.size += <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">rotate</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-string" style="color: #d1f1a9;">"""
将队列的头部变为尾部,循环移动一位
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.size > <span class="hljs-number" style="color: #ffc58f;">0</span>:
self.tail = self.tail.next
<span class="hljs-string" style="color: #d1f1a9;">"""
使用循环链表实现的队列
"""</span>
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class</span> <span class="hljs-title" style="color: #7285b7;">Node</span><span class="hljs-params" style="color: #ffc58f;">()</span>:</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self,next)</span>:</span>
self.element = element
self.next = next
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
self.tail = <span class="hljs-keyword" style="color: #ebbbff;">None</span>
self.size = <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">__len__</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">is_empty</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size == <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">first</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.is_empty():
<span class="hljs-keyword" style="color: #ebbbff;">raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;">'Queue is empty'</span>)
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.tail.next.element
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">dequeue</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.is_empty():
<span class="hljs-keyword" style="color: #ebbbff;">raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;">'Queue is empty'</span>)
old_head = self.tail.next
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.size == <span class="hljs-number" style="color: #ffc58f;">1</span>:
self.tail = <span class="hljs-keyword" style="color: #ebbbff;">None</span>
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
self.tail.next = old_head.next
self.size -= <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> old_head.element
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">enqueue</span><span class="hljs-params" style="color: #ffc58f;">(self,<span class="hljs-keyword" style="color: #ebbbff;">None</span>)
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.is_empty():
new.next = new
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
new.next = self.tail.next
self.tail.next = new
self.tail = new
self.size += <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">rotate</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-string" style="color: #d1f1a9;">"""
将队列的头部变为尾部,循环移动一位
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.size > <span class="hljs-number" style="color: #ffc58f;">0</span>:
self.tail = self.tail.next
<span class="hljs-string" style="color: #d1f1a9;">"""
使用循环链表实现的队列
"""</span>
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class</span> <span class="hljs-title" style="color: #7285b7;">Node</span><span class="hljs-params" style="color: #ffc58f;">()</span>:</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self,next)</span>:</span>
self.element = element
self.next = next
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
self.tail = <span class="hljs-keyword" style="color: #ebbbff;">None</span>
self.size = <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">__len__</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">is_empty</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size == <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">first</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.is_empty():
<span class="hljs-keyword" style="color: #ebbbff;">raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;">'Queue is empty'</span>)
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.tail.next.element
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">dequeue</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.is_empty():
<span class="hljs-keyword" style="color: #ebbbff;">raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;">'Queue is empty'</span>)
old_head = self.tail.next
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.size == <span class="hljs-number" style="color: #ffc58f;">1</span>:
self.tail = <span class="hljs-keyword" style="color: #ebbbff;">None</span>
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
self.tail.next = old_head.next
self.size -= <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> old_head.element
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">enqueue</span><span class="hljs-params" style="color: #ffc58f;">(self,<span class="hljs-keyword" style="color: #ebbbff;">None</span>)
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.is_empty():
new.next = new
<span class="hljs-keyword" style="color: #ebbbff;">else</span>:
new.next = self.tail.next
self.tail.next = new
self.tail = new
self.size += <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">rotate</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-string" style="color: #d1f1a9;">"""
将队列的头部变为尾部,循环移动一位
"""</span>
<span class="hljs-keyword" style="color: #ebbbff;">if</span> self.size > <span class="hljs-number" style="color: #ffc58f;">0</span>:
self.tail = self.tail.next
:
<span class="hljs-string" style="color: #d1f1a9;">"""
具有头哨兵与尾哨兵的双向链表
"""</span>
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class</span> <span class="hljs-title" style="color: #7285b7;">Node</span><span class="hljs-params" style="color: #ffc58f;">()</span>:</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self,prev,next)</span>:</span>
self.element = element
self.prev = prev
self.next = next
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
self.head = self.Node(<span class="hljs-keyword" style="color: #ebbbff;">None</span>,<span class="hljs-keyword" style="color: #ebbbff;">None</span>,<span class="hljs-keyword" style="color: #ebbbff;">None</span>)
self.tail = self.Node(<span class="hljs-keyword" style="color: #ebbbff;">None</span>,<span class="hljs-keyword" style="color: #ebbbff;">None</span>)
self.head.next = self.tail
self.tail.prev = self.head
self.size = <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">__len__</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">is_empty</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size == <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">insert_between</span><span class="hljs-params" style="color: #ffc58f;">(self,e,predecessor,successor)</span>:</span>
new = self.Node(e,successor)
predecessor.next = new
successor.prev = new
self.size += <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> new
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">delete_node</span><span class="hljs-params" style="color: #ffc58f;">(self,node)</span>:</span>
predecessor = node.prev
successor = node.next
predecessor.next = successor
successor.prev = predecessor
element = node.element
self.size -= <span class="hljs-number" style="color: #ffc58f;">1</span>
node.prev=node.next=<span class="hljs-keyword" style="color: #ebbbff;">None</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> element
<span class="hljs-string" style="color: #d1f1a9;">"""
具有头哨兵与尾哨兵的双向链表
"""</span>
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class</span> <span class="hljs-title" style="color: #7285b7;">Node</span><span class="hljs-params" style="color: #ffc58f;">()</span>:</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self,prev,next)</span>:</span>
self.element = element
self.prev = prev
self.next = next
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
self.head = self.Node(<span class="hljs-keyword" style="color: #ebbbff;">None</span>,<span class="hljs-keyword" style="color: #ebbbff;">None</span>,<span class="hljs-keyword" style="color: #ebbbff;">None</span>)
self.tail = self.Node(<span class="hljs-keyword" style="color: #ebbbff;">None</span>,<span class="hljs-keyword" style="color: #ebbbff;">None</span>)
self.head.next = self.tail
self.tail.prev = self.head
self.size = <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">__len__</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">is_empty</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size == <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">insert_between</span><span class="hljs-params" style="color: #ffc58f;">(self,e,predecessor,successor)</span>:</span>
new = self.Node(e,successor)
predecessor.next = new
successor.prev = new
self.size += <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> new
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">delete_node</span><span class="hljs-params" style="color: #ffc58f;">(self,node)</span>:</span>
predecessor = node.prev
successor = node.next
predecessor.next = successor
successor.prev = predecessor
element = node.element
self.size -= <span class="hljs-number" style="color: #ffc58f;">1</span>
node.prev=node.next=<span class="hljs-keyword" style="color: #ebbbff;">None</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> element
<span class="hljs-string" style="color: #d1f1a9;">"""
具有头哨兵与尾哨兵的双向链表
"""</span>
<span class="hljs-class"><span class="hljs-keyword" style="color: #ebbbff;">class</span> <span class="hljs-title" style="color: #7285b7;">Node</span><span class="hljs-params" style="color: #ffc58f;">()</span>:</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self,prev,next)</span>:</span>
self.element = element
self.prev = prev
self.next = next
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;"><a href="https://www.jb51.cc/tag/init/" target="_blank" class="keywords">__init__</a></span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
self.head = self.Node(<span class="hljs-keyword" style="color: #ebbbff;">None</span>,<span class="hljs-keyword" style="color: #ebbbff;">None</span>,<span class="hljs-keyword" style="color: #ebbbff;">None</span>)
self.tail = self.Node(<span class="hljs-keyword" style="color: #ebbbff;">None</span>,<span class="hljs-keyword" style="color: #ebbbff;">None</span>)
self.head.next = self.tail
self.tail.prev = self.head
self.size = <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">__len__</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">is_empty</span><span class="hljs-params" style="color: #ffc58f;">(self)</span>:</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> self.size == <span class="hljs-number" style="color: #ffc58f;">0</span>
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">insert_between</span><span class="hljs-params" style="color: #ffc58f;">(self,e,predecessor,successor)</span>:</span>
new = self.Node(e,successor)
predecessor.next = new
successor.prev = new
self.size += <span class="hljs-number" style="color: #ffc58f;">1</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> new
<span class="hljs-function" style="color: #bbdaff;"><span class="hljs-keyword" style="color: #ebbbff;">def</span> <span class="hljs-title" style="color: #7285b7;">delete_node</span><span class="hljs-params" style="color: #ffc58f;">(self,node)</span>:</span>
predecessor = node.prev
successor = node.next
predecessor.next = successor
successor.prev = predecessor
element = node.element
self.size -= <span class="hljs-number" style="color: #ffc58f;">1</span>
node.prev=node.next=<span class="hljs-keyword" style="color: #ebbbff;">None</span>
<span class="hljs-keyword" style="color: #ebbbff;">return</span> element
如果您也喜欢它,动动您的小指点个赞吧