前言

首先說(shuō)下線性表，線性表是一種最基本，最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，通俗點(diǎn)講就是一維的存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)。

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

• 順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，稱為線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映像；
• 鏈?zhǔn)奖硎局傅氖怯靡唤M任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。而他既可以是連續(xù)的也可以不連續(xù)，是通過(guò)一個(gè)與后繼結(jié)點(diǎn)的連接信息構(gòu)建起來(lái)的。

*順序表（這個(gè)不是本次重點(diǎn)，簡(jiǎn)單介紹一下）

順序表是用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，查找元素是很方便的，但是如果要向其中添加刪除元素就不那么簡(jiǎn)單了。因?yàn)樘砑觿h除元素要先找到那個(gè)位置，由于順序表內(nèi)部是通過(guò)地址的連續(xù)才使他成為一個(gè)表，當(dāng)刪掉元素時(shí)，要把后面的元素全部向前移，填補(bǔ)上空出來(lái)的地址空間；添加元素也是一樣，需要先把該位置后面的元素向后移去，才能在這塊地址上添加元素。

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

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

• 一體式結(jié)構(gòu)
• 分離式結(jié)構(gòu)

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

python中的tuple和list就是采用了順序表的實(shí)現(xiàn)技術(shù)，不過(guò)tuple是不可變的，不支持對(duì)內(nèi)部的操作。而list是一個(gè)元素個(gè)數(shù)可變的線性表，支持添加刪除等操作。list的思想其實(shí)是和C語(yǔ)言中一樣的，只是對(duì)其中的功能進(jìn)行了一些封裝，也就是list的那些屬性。

*鏈?zhǔn)奖?

鏈表，顧名思義，相鄰結(jié)點(diǎn)是通過(guò)鏈來(lái)連接的，那么什么是鏈呢。我們知道，C語(yǔ)言中有指針，指針通過(guò)地址來(lái)找到他的目標(biāo)。如此說(shuō)來(lái)，一個(gè)節(jié)點(diǎn)不僅僅有他的元素，還需要有一個(gè)他下一個(gè)元素的地址。

那么，這里需要指針和地址。python中的指針是什么呢？下面先把這個(gè)放一下，先去理解一下python里面變量標(biāo)識(shí)的實(shí)質(zhì)。

先看一下這個(gè)，為什么a和b的id是一樣的呢？那我再問(wèn)一個(gè)問(wèn)題：python中交換兩個(gè)變量的值時(shí)怎樣來(lái)實(shí)現(xiàn)的？

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

為什么python可以這樣來(lái)賦值呢？下面我再畫(huà)一幅圖。

?

現(xiàn)在是否能理解了呢，變量本身就是存儲(chǔ)的一個(gè)地址，交換他們的值就是把自己的指向更改一下。那么現(xiàn)在知道了標(biāo)識(shí)的含義，我們的指針域該怎么寫(xiě)呢，是不是直接用變量等于下一個(gè)結(jié)點(diǎn)啊。這樣看來(lái)就不復(fù)雜了，接下來(lái)的內(nèi)容就和一般的鏈表一樣了。我在這里說(shuō)這些就是為了弄清楚python是怎么建立鏈接的。

一、單鏈表

那么下面就通過(guò)一個(gè)類來(lái)實(shí)現(xiàn)一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)當(dāng)中包括數(shù)據(jù)域和鏈接域，代碼中實(shí)現(xiàn)了一些常用的功能，比如插入，查找等等。今天主要是說(shuō)一下單鏈表是如何運(yùn)用到python中的，由于我之前沒(méi)有了解過(guò)這些。學(xué)習(xí)了之后，用自己之前的知識(shí)，就可以很方便的運(yùn)用鏈表了。后面的代碼就不過(guò)多解釋了，自己仔細(xì)琢磨一下。有什么不理解的可以留言，我會(huì)盡量詳細(xì)的回復(fù)。

            
#!/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é)點(diǎn)"""

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

'''
上面定義了一個(gè)節(jié)點(diǎn)的類，當(dāng)然也可以直接使用python的一些結(jié)構(gòu)。比如通過(guò)元組（elem, None）
'''


# 下面創(chuàng)建單鏈表，并實(shí)現(xiàn)其應(yīng)有的功能


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

  def __init__(self, node=None): # 使用一個(gè)默認(rèn)參數(shù)，在傳入頭結(jié)點(diǎn)時(shí)則接收，在沒(méi)有傳入時(shí)，就默認(rèn)頭結(jié)點(diǎn)為空
    self.__head = node

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

  def length(self):
    '''鏈表長(zhǎng)度'''
    # cur游標(biāo)，用來(lái)移動(dòng)遍歷節(jié)點(diǎn)
    cur = self.__head
    # count記錄數(shù)量
    count = 0
    while cur != None:
      count += 1
      cur = cur.next
    return count

  def travel(self):
    '''遍歷整個(gè)列表'''
    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)
    # 由于特殊情況當(dāng)鏈表為空時(shí)沒(méi)有next，所以在前面要做個(gè)判斷
    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或者以前，那么都當(dāng)做頭插法來(lái)做
      self.add(item)
    elif pos > self.length() - 1:
      # 如果pos位置比原鏈表長(zhǎng)，那么都當(dāng)做尾插法來(lái)做
      self.append(item)
    else:
      per = self.__head
      count = 0
      while count < pos - 1:
        count += 1
        per = per.next
      # 當(dāng)循環(huán)退出后，pre指向pos-1位置
      node = Node(item)
      node.next = per.next
      per.next = node

  def remove(self, item):
    '''刪除節(jié)點(diǎn)'''
    cur = self.__head
    pre = None
    while cur != None:
      if cur.elem == item:
        # 先判斷該節(jié)點(diǎn)是否是頭結(jié)點(diǎn)
        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é)點(diǎn)是否存在'''
    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)建一個(gè)節(jié)點(diǎn)傳進(jìn)去

  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)鏈表和雙向鏈表

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

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

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

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

今天本來(lái)只想說(shuō)說(shuō)前面那一點(diǎn)點(diǎn)內(nèi)容的，寫(xiě)的寫(xiě)的，后面感覺(jué)不得不說(shuō)一下，不過(guò)也沒(méi)有寫(xiě)的比較完整。大家撿有用的東西來(lái)看。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。