快捷導(dǎo)航

python版本單鏈表實(shí)現(xiàn)代碼

更新時間：2018年09月28日 08:34:14 作者：冬日新雨

這篇文章主要為大家詳細(xì)介紹了python版本單鏈表實(shí)現(xiàn)代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下

今天看了一下數(shù)據(jù)結(jié)構(gòu)的書，發(fā)現(xiàn)其實(shí)數(shù)據(jù)結(jié)構(gòu)沒有幾種，線性表，數(shù)組，字符串，隊列和棧，等等，其實(shí)是一回事，然后就是樹結(jié)構(gòu)，圖結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的理論并不難，主要是要自己寫一下這些數(shù)據(jù)結(jié)構(gòu)以及對應(yīng)的基本的操作方法，這樣就能夠更快的提高。

這一篇blog寫一下線性表。

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

一、順序表

順序表就是相對于表中的數(shù)據(jù)，地址也是順序的，所以可以隨機(jī)存取。但是在操作插入和刪除元素的時候，由于要滿足地址的連續(xù)性，所以要移動很多的元素位置，因此，插入或者刪除一個順序表的元素的時間復(fù)雜度是o(n)。很多時候，在對順序表做合并的時候，需要先對表中的元素進(jìn)行排序，然后再進(jìn)行處理，這樣可以避免每次都從頭進(jìn)行查詢。

二、鏈表

鏈表就失去了順序表的隨機(jī)存取特點(diǎn)，即每次從中取一個元素都要從頭開始找，這樣耗費(fèi)了一些時間，時間復(fù)雜度為o(n)；但是在做插入和刪除，以及兩個鏈表合并的時候，就方便了很多，只需要做一點(diǎn)指針修改就可以了。

鏈表中的每一個元素節(jié)點(diǎn)都包含了數(shù)據(jù)部分和下一個節(jié)點(diǎn)的指針。一般在鏈表的頭部附設(shè)一個頭結(jié)點(diǎn)，而且頭結(jié)點(diǎn)一般不存儲數(shù)據(jù)，而是存放一些長度等附加信息，或者不存儲。

在很多語言中沒有指針這一概念，而有數(shù)組的概念，比如java和python，java中的數(shù)組還要求定義數(shù)組的類型，也就是說必須都是同一類型的數(shù)據(jù)，而python則沒有要求，所以python的list更貼近鏈表的真正含義。這種用數(shù)組描述的鏈表叫做靜態(tài)鏈表。使用靜態(tài)鏈表來描述鏈表對此類語言要方便很多了，本身這些語言都提供了內(nèi)置類來處理鏈表。

除此之外，還有循環(huán)鏈表，雙向鏈表（解決了無法向前搜索的問題，但是在修改指針的時候需要有更多的操作）。

# -*- coding=utf-8 -*-
# 這個例子是Python版本的單鏈表

class Node(object):
  def __init__(self, value, next=0):
    self.value = value
    self.next = next # 指針


class LinkedList(object):
  # 鏈表的數(shù)據(jù)結(jié)構(gòu)
  def __init__(self):
    self.head = 0 # 頭部

  def __getitem__(self, key):
    if self.is_empty():
      print 'Linked list is empty.'
      return
    elif key < 0 or key > self.get_length():
      print 'The given key is wrong.'
      return
    else:
      return self.get_elem(key)

  def __setitem__(self, key, value):
    if self.is_empty():
      print 'Linked list is empty.'
      return
    elif key < 0 or key > self.get_length():
      print 'The given key is wrong.'
      return
    else:
      return self.set_elem(key, value)

  def init_list(self, data): # 按列表給出 data
    self.head = Node(data[0])
    p = self.head # 指針指向頭結(jié)點(diǎn)
    print p, self.head
    for i in data[1:]:
      p.next = Node(i) # 確定指針指向下一個結(jié)點(diǎn)
      p = p.next # 指針滑動向下一個位置
    print self.head.next.next

  def get_length(self):
    length = 0
    p = self.head
    while p != 0: # 0 值就是Node結(jié)點(diǎn)中默認(rèn)的 0 值，表示下一個結(jié)點(diǎn)沒有了，即沒有為其賦值
      length += 1
      p = p.next
    return length

  def is_empty(self):
    if self.head == 0:
      return True
    else:
      return False

  def insert_node(self, index, value):
    if index < 0 or index > self.get_length():
      print 'Can not insert node into the linked list.'
    elif index == 0:
      temp = self.head
      self.head = Node(value, temp)
    else:
      p, post = self.head, self.head
      for i in xrange(index):
        post = p
        p = p.next
      temp = p
      post.next = Node(value, temp)

  def delete_node(self, index):
    if index < 0 or index > self.get_length()-1:
      print "Wrong index number to delete any node."
    elif self.is_empty():
      print "No node can be deleted."
    elif index == 0:
      temp = self.head
      self.head = temp.next
    elif index == self.get_length():
      p = self.head
      for i in xrange(self.get_length()-2):
        p = p.next
      p.next = 0
    else:
      p = self.head
      for i in xrange(index-1):
        p = p.next
      p.next = p.next.next

  def show_linked_list(self): # 打印鏈表中的所有元素
    if self.is_empty():
      print 'This is an empty linked list.'
    else:
      p, container = self.head, []
      for _ in xrange(self.get_length()-1):
        container.append(p.value)
        p = p.next
      container.append(p.value)
      print container

  def clear_linked_list(self): # 將鏈表置空
    self.head = 0

  def get_elem(self, index):
    if self.is_empty():
      print "The linked list is empty. Can not get element."
    elif index < 0 or index > self.get_length()-1:
      print "Wrong index number to get any element."
    else:
      p = self.head
      for _ in xrange(index):
        p = p.next
      return p.value

  def set_elem(self, index, value):
    if self.is_empty():
      print "The linked list is empty. Can not set element."
    elif index < 0 or index > self.get_length()-1:
      print "Wrong index number to set element."
    else:
      p = self.head
      for _ in xrange(index):
        p = p.next
      p.value = value

  def get_index(self, value):
    p = self.head
    for i in xrange(self.get_length()):
      if p.value == value:
        return i
      else:
        p = p.next
    return -1


l = LinkedList()
print "The length of linked list now is: ", l.get_length()
print l.is_empty()
l.init_list([1, 5, 12, "fjd", 45, 999])
print "The length of linked list now is: ", l.get_length()
print l.is_empty()
l.insert_node(4, 100)
l.insert_node(6, "cecil")
l.show_linked_list()
print "The value of index 0 is: ", l.get_elem(0)
l.set_elem(0,1000)
l.show_linked_list()
print "the index of *** is: ", l.get_index(1009)
print "The length of linked list now is: ", l.get_length()
l.delete_node(3)
#l.clear_linked_list()
l.show_linked_list()

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: