用Python实现数据结构之链表

<div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?postid=10336387"&gt;
<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"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;class</span> <span class="hljs-title" style="color: #7285b7;"&gt;Node</span><span class="hljs-params" style="color: #ffc58f;"&gt;()</span>:</span>
    <span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;__init__</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self,element,next)</span>:</span>
        self.element = element
        self.next = next

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;__init__</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    self.head = <span class="hljs-keyword" style="color: #ebbbff;"&gt;None</span>
    self.size = <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;add_head</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self,e)</span>:</span>
    new = self.Node(e,self.head)
    self.head = new
    self.size +=<span class="hljs-number" style="color: #ffc58f;"&gt;1</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;remove_first</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.size == <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>:
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;"&gt;'linkedlist is empty'</span>)
    self.head = self.head.next
    self.size -= <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>

<span class="hljs-string" style="color: #d1f1a9;"&gt;"""
使用循环链表实现的队列
"""</span>

<span class="hljs-class"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;class</span> <span class="hljs-title" style="color: #7285b7;"&gt;Node</span><span class="hljs-params" style="color: #ffc58f;"&gt;()</span>:</span>
    <span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;__init__</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self,next)</span>:</span>
        self.element = element
        self.next = next

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;__init__</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    self.tail = <span class="hljs-keyword" style="color: #ebbbff;"&gt;None</span>
    self.size = <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;__len__</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self.size

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;is_empty</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self.size == <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;first</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.is_empty():
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;"&gt;'Queue is empty'</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> self.tail.next.element

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;dequeue</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.is_empty():
        <span class="hljs-keyword" style="color: #ebbbff;"&gt;raise</span> Empty(<span class="hljs-string" style="color: #d1f1a9;"&gt;'Queue is empty'</span>)
    old_head = self.tail.next
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.size == <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>:
        self.tail = <span class="hljs-keyword" style="color: #ebbbff;"&gt;None</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
        self.tail.next = old_head.next
    self.size -= <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;return</span> old_head.element

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;enqueue</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self,<span class="hljs-keyword" style="color: #ebbbff;"&gt;None</span>)
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.is_empty():
        new.next = new
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;else</span>:
        new.next = self.tail.next
        self.tail.next = new
    self.tail = new
    self.size += <span class="hljs-number" style="color: #ffc58f;"&gt;1</span>

<span class="hljs-function" style="color: #bbdaff;"&gt;<span class="hljs-keyword" style="color: #ebbbff;"&gt;def</span> <span class="hljs-title" style="color: #7285b7;"&gt;rotate</span><span class="hljs-params" style="color: #ffc58f;"&gt;(self)</span>:</span>
    <span class="hljs-string" style="color: #d1f1a9;"&gt;"""
    将队列的头部变为尾部，循环移动一位
    """</span>
    <span class="hljs-keyword" style="color: #ebbbff;"&gt;if</span> self.size > <span class="hljs-number" style="color: #ffc58f;"&gt;0</span>:
        self.tail = self.tail.next