前言

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

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

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

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

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

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

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

• 一體式結構
• 分離式結構

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

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

*鏈式表

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

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

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

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

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

?

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

一、單鏈表

那么下面就通過一個類來實現一個節點，節點當中包括數據域和鏈接域，代碼中實現了一些常用的功能，比如插入，查找等等。今天主要是說一下單鏈表是如何運用到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):
  """節點"""

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

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


# 下面創建單鏈表，并實現其應有的功能


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

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

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

  def length(self):
    '''鏈表長度'''
    # cur游標，用來移動遍歷節點
    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
      # 當循環退出后，pre指向pos-1位置
      node = Node(item)
      node.next = per.next
      per.next = node

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

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


if __name__ == "__main__":

    # node = Node(100) # 先創建一個節點傳進去

  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()
          

二、單向循環鏈表和雙向鏈表

與單鏈表相關聯的，還有單向循環鏈表和雙向鏈表：

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

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

雙向鏈表的插入和刪除等等操作，都要注意，不要把存儲的地址信息丟了，仔細考慮好兩邊的指向，先把誰鏈接上去，再鏈接誰。

今天本來只想說說前面那一點點內容的，寫的寫的，后面感覺不得不說一下，不過也沒有寫的比較完整。大家撿有用的東西來看。

總結

以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對腳本之家的支持。