1.4 链表python（19段代码）
<h1>链表的构建</h1>
<pre><code class="language-python">class LNode:
def __init__(self, data=None):
self.data = data
self.next = None
class Link:
def __init__(self):
self.head = LNode()</code></pre>
<p> </p>
<h1>链表的操作</h1>
<h1>辅助操作</h1>
<h2>【格式化输出】</h2>
<p>简单的：</p>
<pre><code class="language-python">class Link:
def show(self):
h = self.head
while h.next:
print(h.next.data, end=&#039; &#039;)
h = h.next</code></pre>
<p> </p>
<p>高级的：</p>
<pre><code class="language-python">class Link:
def __str__(self):
s = &#039;&#039;
h = self.head
while h.next:
s += str(h.next.data) + &#039; &#039;
h = h.next
return s</code></pre>
<p> </p>
<p>其中<strong>str</strong>是python对象的特殊方法，当调用print的时候，自动调用<strong>str</strong>的返回值。</p>
<p> </p>
<h2>【判断是不是空】</h2>
<pre><code class="language-python">class Link:
def isempty(self):
return self.head.next is None</code></pre>
<p> </p>
<p> </p>
<h1>增加元素</h1>
<h2>【头部添加】</h2>
<pre><code class="language-python">class Link:
def append_head(self, m):
node = LNode(m)
node.next = self.head.next
self.head.next = node
</code></pre>
<p> </p>
<h2>【尾部添加】</h2>
<pre><code class="language-python">class Link:
def append_tail(self, m):
node = LNode(m)
h = self.head
while h.next:
h = h.next
h.next = node</code></pre>
<p> </p>
<h2>【插入】</h2>
<pre><code class="language-python">class Link:
def insert(self, i, k):
if i &lt; 0:
return 1
h = self.head
for j in range(i):
if h:
h = h.next
else:
return 1
if h:
node = LNode(k)
node.next = h.next
h.next = node
else:
return 1</code></pre>
<p> </p>
<h2>【拼接】</h2>
<pre><code class="language-python">class Link:
def extend(self, other):
h = self.head
while h.next:
h = h.next
h.next = other.head.next</code></pre>
<p> </p>
<p> </p>
<h1>删除元素</h1>
<h2>【弹出一个元素】</h2>
<pre><code class="language-python">class Link:
def pop(self):
if self.isempty():
return None
h = self.head
while h.next.next:
h = h.next
k = h.next.data
h.next = None
return k
</code></pre>
<p> </p>
<h2>【删除第i个】</h2>
<pre><code class="language-python">class Link:
def popi(self, i):
if self.isempty():
return None
if i&lt;0:
return None
h = self.head
for j in range(i):
if h.next is None:
return None
h = h.next
if h.next:
k = h.next.data
h.next = h.next.next
return k
else:
return None
</code></pre>
<p> </p>
<h2>【删除n这个值】</h2>
<pre><code class="language-python">class Link:
def remove(self, n):
h = self.head
while h.next:
if h.next.data == n:
h.next = h.next.next
else:
h = h.next</code></pre>
<p> </p>
<h2>【清空】</h2>
<pre><code class="language-python">class Link:
def clear(self):
self.head.next = None
</code></pre>
<p> </p>
<h1>修改</h1>
<p>【修改第i个值】</p>
<pre><code class="language-python">class Link:
def set(self, i, x):
if self.isempty():
return None
if i&lt;0:
return None
h = self.head
for j in range(i):
if h.next is None:
return None
h = h.next
if h.next:
h.next.data = x
else:
return None
</code></pre>
<p> </p>
<h2>【替换x为y】</h2>
<pre><code class="language-python">class Link:
def replace(self, x, y):
h = self.head
while h.next:
if h.next.data == x:
h.next.data = y
h = h.next
</code></pre>
<p> </p>
<h2>【翻转】</h2>
<p>略，一般不对单链表进行翻转，思考：为什么？</p>
<p> </p>
<h1>查询</h1>
<h2>【获取长度】</h2>
<pre><code class="language-python">class Link:
def length(self):
h = self.head
count = 0
while h.next:
count += 1
h = h.next
return count
</code></pre>
<p> </p>
<h2>【获取最大值/最小值】</h2>
<pre><code class="language-python">class Link:
def max(self):
if self.isempty():
return None
h = self.head
res = h.next.data
while h.next:
res = h.next.data if h.next.data&gt;res else res
h = h.next
return res</code></pre>
<p> </p>
<h2>【判断某个值在不在里面】</h2>
<pre><code class="language-python">class Link:
def has(self, x):
if self.isempty():
return False
h = self.head
while h.next:
if h.next.data == x:
return True
h = h.next
return False</code></pre>
<p> </p>
<h2>【获取某个位置的值】</h2>
<pre><code class="language-python">class Link:
def get(self, i):
if self.isempty():
return None
if i&lt;0:
return None
h = self.head
for j in range(i):
if h.next is None:
return None
h = h.next
if h.next:
return h.next.data
else:
return None
</code></pre>
<p> </p>
<h2>【获取某个值的位置】</h2>
<pre><code class="language-python">class Link:
def index(self, x):
if self.isempty():
return -1
h = self.head
count = 0
while h.next:
if h.next.data == x:
return count
h = h.next
count += 1
return -1</code></pre>