打牢地基-鏈表

章節

  • 動態數組 & 棧 & 隊列 與 鏈表的不同
  • 鏈表特性 & 圖示
  • 鏈表實現 & 各操作時間複雜度分析

動態數組 & 棧 & 隊列 與 鏈表的不同

重要 動態數組、棧、隊列 底層依託的都是靜態數組 鏈表是天然的動態數據結構

鏈表重要性 & 簡介 & 圖示

重要性:

  1. 1. 真正的動態數據結構
  2. 2. 最簡單的動態數據結構
  3. 3. 涉及更深入的引用(或者指針)
  4. 4. 更深入的理解遞歸 （天然具有遞歸屬性，node.next is node ）
  5. 5. 輔助組成其他數據結構 - 棧、隊列也可以用鏈表實現，還有hashmap

鏈表 – LinkedList

  1. 1. 數據存儲在節點中
  2. class Node {
  3. // 存儲具體的數據
  4. E e;
  5. // 指向下一個node的引用
  6. Node next;
  7. }

鏈表數據結構如下圖所示:

優點: 1.真正的動態，不需要處理固定容量問題 2.增刪數據非常方便

缺點:

  1. 喪失了隨機訪問的缺點

鏈表實現 & 各操作時間複雜度分析

鏈表實現 – python 版

注意: 關鍵點: 找到要插入節點的前一個節點 LinkedList – (head實現)

#!/usr/bin/env python    # -*- coding: utf-8 -*-    """    # @Time    : 2020/2/5 下午3:44    # @Author  : [email protected]    # @Site    :    # @File    : LinkedList.py    # @Software: PyCharm    # 自己實現鏈表元素需要的節點    # head 版    """    class Node:     def __init__(self, e=None, next=None):            self.e = e            self.next = next           def to_string(self):     return self.e        class LinkedList:     """        鏈表中的成員變數，head 指向鏈表中頭節點，size 是鏈表中元素的個數        """       def __init__(self):            self._head = None            self._size = 0       def get_size(self):     return self._size       def is_empty(self):     return self._size == 0       def add_first(self, val):     """            頭插法            :param node:            :return:            """            node = Node(e=val)            node.next = self._head            self._head = node     # 簡寫     # self._head = Node(val, self._head)            self._size += 1           def add(self, index, e):     if index < 0 or index > self._size:     raise (Exception, 'Add failed! Illegal index')     if index == 0:     # 這步操作可以通過虛擬頭節點屏蔽掉                self.add_first(e)     else:                prev = self._head     for i in range(0, index - 1):                    prev = prev.next                new_node = Node(e=e)                new_node.next = prev.next                prev.next = new_node     # 簡寫                prev.next = Node(e, prev.next)            self._size += 1           def add_last(self, e):            self.add(self._size, e)

LinkedList – (dummy_head 虛擬節點實現)

#!/usr/bin/env python  # -*- coding: utf-8 -*-  """  # @Time    : 2020/2/5 下午3:44  # @Author  : [email protected]  # @Site    :  # @File    : LinkedList.py  # @Software: PyCharm  # 自己實現鏈表元素需要的節點  # dummy_head(虛擬頭節點)版  # 刪除和新增都需要找到前一個節點  """  class Node:   def __init__(self, e=None, next=None):          self.e = e          self.next = next   def to_string(self):   return self.e  class LinkedList:   """      鏈表中的成員變數，head 指向鏈表中頭節點，size 是鏈表中元素的個數      """   def __init__(self):          self._dummy_head = Node(None, None)          self._size = 0   def get_size(self):   return self._size   def is_empty(self):   return self._size == 0   def add(self, index, e):   """          實質是佔用原有index元素的位置，並將原有index元素向後移動          :param index:          :param e:          :return:          """   if index < 0 or index > self._size:   raise (Exception, 'Add failed! Illegal index')          prev = self._dummy_head   for i in range(0, index):              prev = prev.next          new_node = Node(e=e)          new_node.next = prev.next          prev.next = new_node   # 簡寫   # prev.next = Node(e, prev.next)          self._size += 1   def add_first(self, e):   """          頭插法          :param e:          :return:          """          self.add(0, e)   def add_last(self, e):          self.add(self._size, e)   def get(self, index):   if index < 0 or index > self._size:   raise (Exception, 'Get failed! Illegal index')   # 鏈表的真實頭節點          cur = self._dummy_head.next   for i in range(0, index):              cur = cur.next   return cur.e   def get_first(self):   return self.get(0)   def get_last(self):   return self.get(self._size - 1)   # 更新操作   def set(self, index, e):   if index < 0 or index > self._size:   raise (Exception, 'set failed! Illegal index')          cur = self._dummy_head.next   for i in range(0, index):              cur = cur.next          cur.e = e   # 刪除操作   def remove(self, index):   if index < 0 or index > self._size:   raise (Exception, 'set failed! Illegal index')          prev = self._dummy_head   for i in range(0, index):              prev = prev.next          del_node = prev.next          prev.next = del_node.next          del_node.next = None          self._size -= 1   return del_node.e   def remove_first(self):   return self.remove(0)   def remove_last(self):   return self.remove(self._size - 1)   # 查找鏈表中是否存在某個元素   def contains(self, e):          cur = self._dummy_head.next   while cur is not None:   if cur.e == e:   return True              cur = cur.next   return False   def to_string(self):          res_linkedlist_arr = []          res_linkedlist_arr.append('LinkedList:size = %d  ' % self._size)          cur = self._dummy_head.next   while cur is not None:              val = cur.e   if isinstance(val, int):                  val = str(val)              res_linkedlist_arr.append(val + ' -> ')              cur = cur.next          res_linkedlist_arr.append(' NULL ')   return "".join(res_linkedlist_arr)  if __name__ == '__main__':      a = 1      linkedList = LinkedList()   for i in range(0, 5):          linkedList.add_first(i)   print(linkedList.to_string())      linkedList.set(1, 2)   print(linkedList.to_string())      linkedList.add(5, 10)   print(linkedList.to_string())      linkedList.remove_first()   print(linkedList.to_string())      linkedList.remove_last()   print(linkedList.to_string())      linkedList.remove(1)   print(linkedList.to_string()

各操作時間複雜度分析

add 操作

add_last  O(n) 複雜度    add_first O(1) 複雜度    add(index, e) O(n/2) 即 O(n) 的複雜度

remove 操作

remove_last O(n)    remove_first O(1)    remove(index,e) O(n/2) 即 O(n) 的複雜度

set 操作

set(index,e)  O(n)

get

get(index) O(n)    contains(e) O(n)

增刪改查的時間複雜度都是O(n) 級別的，單對鏈表頭節點(即虛擬頭節點的下一個實體節點)，時間複雜度是O(1)

VirMach 便宜 VPS

QNews

QNews