數據結構是計算機科學必須掌握的一門學問，之前很多的教材都是用C語言實現鏈表，因為c有指針，可以很方便的控制內存，很方便就實現鏈表，其他的語言，則沒那么方便，有很多都是用模擬鏈表，不過這次，我不是用模擬鏈表來實現，因為python是動態語言，可以直接把對象賦值給新的變量。

好了，在說我用python實現前，先簡單說說鏈表吧。在我們存儲一大波數據時，我們很多時候是使用數組，但是當我們執行插入操作的時候就是非常麻煩，看下面的例子，有一堆數據1,2,3,5,6,7我們要在3和5之間插入4,如果用數組，我們會怎么做？當然是將5之后的數據往后退一位，然后再插入4,這樣非常麻煩，但是如果用鏈表，我就直接在3和5之間插入4就行，聽著就很方便。

那么鏈表的結構是怎么樣的呢？顧名思義，鏈表當然像鎖鏈一樣，由一節節節點連在一起，組成一條數據鏈。

鏈表的節點的結構如下：

data為自定義的數據，next為下一個節點的地址。

鏈表的結構為，head保存首位節點的地址：

接下來我們來用python實現鏈表

python實現鏈表

首先，定義節點類Node：

class Node:  '''  data: 節點保存的數據  _next: 保存下一個節點對象  '''  def __init__(self, data, pnext=None):    self.data = data    self._next = pnext  def __repr__(self):    '''    用來定義Node的字符輸出，    print為輸出data    '''    return str(self.data)

然后，定義鏈表類：

鏈表要包括：

屬性：

鏈表頭：head

鏈表長度：length

方法：

判斷是否為空: isEmpty()

def isEmpty(self):  return (self.length == 0

增加一個節點(在鏈表尾添加): append()

def append(self, dataOrNode):  item = None  if isinstance(dataOrNode, Node):    item = dataOrNode  else:    item = Node(dataOrNode)  if not self.head:    self.head = item    self.length += 1  else:    node = self.head    while node._next:      node = node._next    node._next = item    self.length += 1

刪除一個節點: delete()

#刪除一個節點之后記得要把鏈表長度減一def delete(self, index):  if self.isEmpty():    print "this chain table is empty."    return  if index < 0 or index >= self.length:    print 'error: out of index'    return  #要注意刪除第一個節點的情況  #如果有空的頭節點就不用這樣  #但是我不喜歡弄頭節點  if index == 0:    self.head = self.head._next    self.length -= 1    return  #prev為保存前導節點  #node為保存當前節點  #當j與index相等時就  #相當于找到要刪除的節點  j = 0  node = self.head  prev = self.head  while node._next and j < index:    prev = node    node = node._next    j += 1  if j == index:    prev._next = node._next    self.length -= 1