|
<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;">链表与栈，队列不一样，它是由一个个节点构成的，每个节点存储着本身的一些信息，也存储着其他一个或多个节点的引用，可以从一个节点找到其他的节点，节点与节点之间就像是有链连在一起一样，这种数据结构就叫做链表
<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;">__init__</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;">__init__</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>
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">这个链表没有保存尾指针，并且添加与删除只在头部进行，节点类的定义嵌套在了其中
<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-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;">__init__</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;">__init__</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
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">这里需要注意些的地方就是队列的插入与删除，因为涉及到节点指向的变换，其实手动画画图的话还是非常容易理解的
<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;">前边的单向链表，循环链表，都是每一个节点为其后继节点维护一个引用，这样就会导致一些限制，即如果给定链表中的一个节点的引用，我们很难将其删掉，因为它并没有存储前驱节点的引用，对于这样的问题，我们会想到使用一种既存储前驱也存储后继的节点，这就是双向链表
<h3 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px 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;">之前的两种链表都是直接存储了头结点的引用，这样使我们在执行某些方法时，必须要判断一下是不是头结点，是不是为节点，为了避免这些特殊情况我们可以在链表的头部与尾部分别追加一个存储为空的头部节点与存储为空的尾部节点，我们叫它头哨兵与尾哨兵，这两个哨兵并不在序列中，并且只占用很少的空间，但却可以简化许多有关节点的操作。
<h3 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px solid #aaaaaa;">具体实现
:
<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;">__init__</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;">__init__</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
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">insert_between传入的是元素与前驱节点和后继节点
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">delete_node传入的是要删除的节点
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
