python實現單鏈表的方法示例

更新時間：2019年09月03日 09:25:29 作者：漁單渠

這篇文章主要給大家介紹了關于python實現單鏈表的相關資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用python具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧

前言

首先說下線性表，線性表是一種最基本，最簡單的數據結構，通俗點講就是一維的存儲數據的結構。

線性表分為順序表和鏈接表：

順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數據元素，稱為線性表的順序存儲結構或順序映像；
鏈式表示指的是用一組任意的存儲單元存儲線性表中的數據元素，稱為線性表的鏈式存儲結構。而他既可以是連續(xù)的也可以不連續(xù)，是通過一個與后繼結點的連接信息構建起來的。

*順序表（這個不是本次重點，簡單介紹一下）

順序表是用一段連續(xù)的存儲單元依次存儲數據元素，查找元素是很方便的，但是如果要向其中添加刪除元素就不那么簡單了。因為添加刪除元素要先找到那個位置，由于順序表內部是通過地址的連續(xù)才使他成為一個表，當刪掉元素時，要把后面的元素全部向前移，填補上空出來的地址空間；添加元素也是一樣，需要先把該位置后面的元素向后移去，才能在這塊地址上添加元素。

以C語言為例：順序表可以通過一個數組來表示，每創(chuàng)建一個數組就對應給他分配一塊內存。當然除了靜態(tài)分配空間，還可以動態(tài)擴展。后續(xù)的操作要在這塊內存上進行，一般都需要移動數組元素，復雜度會很高。

在python中，順序表還有兩種表示方式：

一體式結構
分離式結構

這里的一體和分離是指表中的元素集合，和為實現正確操作而需記錄的信息，這兩部分是在同一塊空間還是在旁邊的一塊新的空間中。

python中的tuple和list就是采用了順序表的實現技術，不過tuple是不可變的，不支持對內部的操作。而list是一個元素個數可變的線性表，支持添加刪除等操作。list的思想其實是和C語言中一樣的，只是對其中的功能進行了一些封裝，也就是list的那些屬性。

*鏈式表

鏈表，顧名思義，相鄰結點是通過鏈來連接的，那么什么是鏈呢。我們知道，C語言中有指針，指針通過地址來找到他的目標。如此說來，一個節(jié)點不僅僅有他的元素，還需要有一個他下一個元素的地址。

那么，這里需要指針和地址。python中的指針是什么呢？下面先把這個放一下，先去理解一下python里面變量標識的實質。

先看一下這個，為什么a和b的id是一樣的呢？那我再問一個問題：python中交換兩個變量的值時怎樣來實現的？

1 a = 10
2 b = 20
3 a,b = b,a

為什么python可以這樣來賦值呢？下面我再畫一幅圖。

現在是否能理解了呢，變量本身就是存儲的一個地址，交換他們的值就是把自己的指向更改一下。那么現在知道了標識的含義，我們的指針域該怎么寫呢，是不是直接用變量等于下一個結點啊。這樣看來就不復雜了，接下來的內容就和一般的鏈表一樣了。我在這里說這些就是為了弄清楚python是怎么建立鏈接的。

一、單鏈表

那么下面就通過一個類來實現一個節(jié)點，節(jié)點當中包括數據域和鏈接域，代碼中實現了一些常用的功能，比如插入，查找等等。今天主要是說一下單鏈表是如何運用到python中的，由于我之前沒有了解過這些。學習了之后，用自己之前的知識，就可以很方便的運用鏈表了。后面的代碼就不過多解釋了，自己仔細琢磨一下。有什么不理解的可以留言，我會盡量詳細的回復。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date  : 2018-06-12 11:23:21
# @Author : yudanqu (943775910@qq.com)
# @Link  : https://www.cnblogs.com/yudanqu/
# @Version : $Id$


class Node(object):
  """節(jié)點"""

  def __init__(self, elem):
    self.elem = elem
    self.next = None # 初始設置下一節(jié)點為空

'''
上面定義了一個節(jié)點的類，當然也可以直接使用python的一些結構。比如通過元組（elem, None）
'''


# 下面創(chuàng)建單鏈表，并實現其應有的功能


class SingleLinkList(object):
  """單鏈表"""

  def __init__(self, node=None): # 使用一個默認參數，在傳入頭結點時則接收，在沒有傳入時，就默認頭結點為空
    self.__head = node

  def is_empty(self):
    '''鏈表是否為空'''
    return self.__head == None

  def length(self):
    '''鏈表長度'''
    # cur游標，用來移動遍歷節(jié)點
    cur = self.__head
    # count記錄數量
    count = 0
    while cur != None:
      count += 1
      cur = cur.next
    return count

  def travel(self):
    '''遍歷整個列表'''
    cur = self.__head
    while cur != None:
      print(cur.elem, end=' ')
      cur = cur.next
    print("\n")

  def add(self, item):
    '''鏈表頭部添加元素'''
    node = Node(item)
    node.next = self.__head
    self.__head = node

  def append(self, item):
    '''鏈表尾部添加元素'''
    node = Node(item)
    # 由于特殊情況當鏈表為空時沒有next，所以在前面要做個判斷
    if self.is_empty():
      self.__head = node
    else:
      cur = self.__head
      while cur.next != None:
        cur = cur.next
      cur.next = node

  def insert(self, pos, item):
    '''指定位置添加元素'''
    if pos <= 0:
        # 如果pos位置在0或者以前，那么都當做頭插法來做
      self.add(item)
    elif pos > self.length() - 1:
      # 如果pos位置比原鏈表長，那么都當做尾插法來做
      self.append(item)
    else:
      per = self.__head
      count = 0
      while count < pos - 1:
        count += 1
        per = per.next
      # 當循環(huán)退出后，pre指向pos-1位置
      node = Node(item)
      node.next = per.next
      per.next = node

  def remove(self, item):
    '''刪除節(jié)點'''
    cur = self.__head
    pre = None
    while cur != None:
      if cur.elem == item:
        # 先判斷該節(jié)點是否是頭結點
        if cur == self.__head:
          self.__head = cur.next
        else:
          pre.next = cur.next
        break
      else:
        pre = cur
        cur = cur.next

  def search(self, item):
    '''查找節(jié)點是否存在'''
    cur = self.__head
    while not cur:
      if cur.elem == item:
        return True
      else:
        cur = cur.next
    return False


if __name__ == "__main__":

    # node = Node(100) # 先創(chuàng)建一個節(jié)點傳進去

  ll = SingleLinkList()
  print(ll.is_empty())
  print(ll.length())

  ll.append(3)
  ll.add(999)
  ll.insert(-3, 110)
  ll.insert(99, 111)
  print(ll.is_empty())
  print(ll.length())
  ll.travel()
  ll.remove(111)
  ll.travel()

二、單向循環(huán)鏈表和雙向鏈表

與單鏈表相關聯的，還有單向循環(huán)鏈表和雙向鏈表：

單向循環(huán)鏈表：在單鏈表的基礎上，再多一個由尾節(jié)點指向首節(jié)點的鏈接，首節(jié)點是指鏈表的第一個存數據的結點，而頭結點是指指向第一個存數據的結點的那個東西，僅有個鏈接域，而不是真正存儲內容的鏈表結點。需要注意的是，循環(huán)鏈表中，一些功能的創(chuàng)建是和單鏈表不一樣的，比如判空、判滿，它是循環(huán)的該怎么判斷呢？這些內容可以在上面給出的單鏈表的實現中進行修改獲得，可以試一下。

雙向鏈表：與單鏈表相比，這個新增的特性就是雙向?？梢詮那懊嫦蚝竺?zhèn)鬟f，也可以從后面向前面?zhèn)鬟f，這個前面和后面是我們自己定義的，認為從一端到另一端是正向，那么倒過來則相反。這個雙向鏈表的實現和單鏈表也是基本上一樣的。單向鏈表是除了數據域再添加一個鏈接域，來指向下一個結點。那么同樣的道理，雙向鏈表就再添加一個指向前一個結點的鏈接不就好了。這個時候再創(chuàng)建鏈表的時候就要把每個節(jié)點與前驅結點以及后繼結點的鏈接建立好。