數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)基礎(chǔ)的必修內(nèi)容，也是很多大型互聯(lián)網(wǎng)企業(yè)面試的必考題。可想而知，它在計(jì)算機(jī)領(lǐng)域的重要性。

然而很多計(jì)算機(jī)專(zhuān)業(yè)的同學(xué)，都僅僅是了解數(shù)據(jù)結(jié)構(gòu)的相關(guān)理論，卻無(wú)法用代碼實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)。

今日整理了一份常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的 Python 實(shí)現(xiàn)，希望大家能夠參考代碼，親自動(dòng)手通過(guò)代碼實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)，以鞏固知識(shí)加深理解。

以下內(nèi)容整理于 《Python 實(shí)現(xiàn)各種常用算法》

棧

          
            class Stack(object):
    def __init__(self, limit=10):
        self.stack = [] #存放元素
        self.limit = limit #棧容量極限
    def push(self, data): #判斷棧是否溢出
        if len(self.stack) >= self.limit:
            print('StackOverflowError')
            pass
        self.stack.append(data)
    def pop(self):
        if self.stack:
            return self.stack.pop()
        else:
            raise IndexError('pop from an empty stack') #空棧不能被彈出
    def peek(self): #查看堆棧的最上面的元素
        if self.stack:
            return self.stack[-1]
    def is_empty(self): #判斷棧是否為空
        return not bool(self.stack)
    def size(self): #返回棧的大小
        return len(self.stack)

          
        

單鏈表

          
            class Node:  
    def __init__(self, data):
        self.data = data  
        self.next = None  
class Linked_List:
    def __init__(self):
        self.head = None
    def initlist(self,data_list):    #鏈表初始化函數(shù)
        self.head=Node(data_list[0])   #創(chuàng)建頭結(jié)點(diǎn)
        temp=self.head
        for i in data_list[1:]: #逐個(gè)為 data 內(nèi)的數(shù)據(jù)創(chuàng)建結(jié)點(diǎn), 建立鏈表
            node=Node(i)
            temp.next=node
            temp=temp.next
    def is_empty(self):  #判斷鏈表是否為空
        if self.head.next==None:
            print("Linked_list is empty")
            return True
        else:
            return False
    def get_length(self):  #獲取鏈表的長(zhǎng)度
        temp=self.head #臨時(shí)變量指向隊(duì)列頭部
        length=0 #計(jì)算鏈表的長(zhǎng)度變量
        while temp!=None:
            length=length+1
            temp=temp.next
        return length #返回鏈表的長(zhǎng)度
    def insert(self,key,value): #鏈表插入數(shù)據(jù)函數(shù)
        if key<0 or key>self.get_length()-1:
            print("insert error")
        temp=self.head
        i=0
        while i<=key: #遍歷找到索引值為 key 的結(jié)點(diǎn)后, 在其后面插入結(jié)點(diǎn)
            pre=temp
            temp=temp.next
            i=i+1
        node=Node(value)
        pre.next=node
        node.next=temp
    def print_list(self):   #遍歷鏈表，并將元素依次打印出來(lái)
        print("linked_list:")
        temp=self.head
        new_list=[]
        while temp is not None:
            new_list.append(temp.data)
            temp=temp.next
        print(new_list)
    def remove(self,key):  #鏈表刪除數(shù)據(jù)函數(shù)
        if key<0 or key>self.get_length()-1:
            print("insert error")
        i=0
        temp=self.head
        while temp !=None:  #遍歷找到索引值為 key 的結(jié)點(diǎn)
            pre=temp
            temp=temp.next
            i=i+1
            if i==key:
                pre.next=temp.next
                temp=None
                return True
        pre.next=None
    def reverse(self): #將鏈表反轉(zhuǎn)
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev
          
        

雙鏈表

          
            class Node(object):
    # 雙向鏈表節(jié)點(diǎn)
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None
class DLinkList(object):
    # 雙向鏈表
    def __init__(self):
        self._head = None
    def is_empty(self):
        # 判斷鏈表是否為空
        return self._head == None
    def get_length(self):
        # 返回鏈表的長(zhǎng)度
        cur = self._head
        count = 0
        while cur != None:
            count=count+1
            cur = cur.next
        return count
    def travel(self):
        # 遍歷鏈表
        cur = self._head
        while cur != None:
            print(cur.item)
            cur = cur.next
        print("")
    def add(self, item):
        # 頭部插入元素
        node = Node(item)
        if self.is_empty():
            # 如果是空鏈表，將_head指向node
            self._head = node
        else:
            # 將node的next指向_head的頭節(jié)點(diǎn)
            node.next = self._head
            # 將_head的頭節(jié)點(diǎn)的prev指向node
            self._head.prev = node
            # 將_head 指向node
            self._head = node
    def append(self, item):
        # 尾部插入元素
        node = Node(item)
        if self.is_empty():
            # 如果是空鏈表，將_head指向node
            self._head = node
        else:
            # 移動(dòng)到鏈表尾部
            cur = self._head
            while cur.next != None:
                cur = cur.next
            # 將尾節(jié)點(diǎn)cur的next指向node
            cur.next = node
            # 將node的prev指向cur
            node.prev = cur
    def search(self, item):
        # 查找元素是否存在
        cur = self._head
        while cur != None:
            if cur.item == item:
                return True
            cur = cur.next
        return False
    def insert(self, pos, item):
        # 在指定位置添加節(jié)點(diǎn)
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            count = 0
            # 移動(dòng)到指定位置的前一個(gè)位置
            while count < (pos-1):
                count += 1
                cur = cur.next
            # 將node的prev指向cur
            node.prev = cur
            # 將node的next指向cur的下一個(gè)節(jié)點(diǎn)
            node.next = cur.next
            # 將cur的下一個(gè)節(jié)點(diǎn)的prev指向node
            cur.next.prev = node
            # 將cur的next指向node
            cur.next = node
    def remove(self, item):
        # 刪除元素
        if self.is_empty():
            return
        else:
            cur = self._head
            if cur.item == item:
                # 如果首節(jié)點(diǎn)的元素即是要?jiǎng)h除的元素
                if cur.next == None:
                    # 如果鏈表只有這一個(gè)節(jié)點(diǎn)
                    self._head = None
                else:
                    # 將第二個(gè)節(jié)點(diǎn)的prev設(shè)置為None
                    cur.next.prev = None
                    # 將_head指向第二個(gè)節(jié)點(diǎn)
                    self._head = cur.next
                return
            while cur != None:
                if cur.item == item:
                    # 將cur的前一個(gè)節(jié)點(diǎn)的next指向cur的后一個(gè)節(jié)點(diǎn)
                    cur.prev.next = cur.next
                    # 將cur的后一個(gè)節(jié)點(diǎn)的prev指向cur的前一個(gè)節(jié)點(diǎn)
                    cur.next.prev = cur.prev
                    break
                cur = cur.next
          
        

隊(duì)列（鏈表形式實(shí)現(xiàn)）

          
            class Node(object):
    def __init__(self,elem,next=None):
        self.elem = elem #表示對(duì)應(yīng)的元素值
        self.next=next #表示下一個(gè)鏈接的鏈點(diǎn)
class Queue(object):
    def __init__(self):
        self.head = None #頭部鏈點(diǎn)為 None
        self.rear = None #尾部鏈點(diǎn)為 None
    def is_empty(self):
        return self.head is None #判斷隊(duì)列是否為空
    def enqueue(self, elem):
        p = Node(elem) #初始化一個(gè)新的點(diǎn)
        if self.is_empty():
            self.head = p #隊(duì)列頭部為新的鏈點(diǎn)
            self.rear = p #隊(duì)列尾部為新的鏈點(diǎn)
        else:
            self.rear.next = p #隊(duì)列尾部的后繼是這個(gè)新的點(diǎn)
            self.rear =p #然后讓隊(duì)列尾部指針指向這個(gè)新的點(diǎn)
    def dequeue(self):
        if self.is_empty(): #判斷隊(duì)列是否為空
            print('Queue_is_empty') #若隊(duì)列為空，則退出 dequeue 操作
        else:
            result = self.head.elem #result為隊(duì)列頭部元素
            self.head = self.head.next #改變隊(duì)列頭部指針位置
            return result #返回隊(duì)列頭部元素
    def peek(self):
        if self.is_empty(): #判斷隊(duì)列是否為空
            print('NOT_FOUND') #為空則返回 NOT_FOUND
        else:
            return self.head.elem #返回隊(duì)列頭部元素
    def print_queue(self):
        print("queue:")
        temp=self.head
        myqueue=[] #暫時(shí)存放隊(duì)列數(shù)據(jù)
        while temp is not None:
            myqueue.append(temp.elem)
            temp=temp.next
        print(myqueue)
          
        

隊(duì)列（數(shù)組形式實(shí)現(xiàn)）

          
            class Queue():
    def __init__(self):
        self.entries = [] #表示隊(duì)列內(nèi)的參數(shù)
        self.length = 0 #表示隊(duì)列的長(zhǎng)度
        self.front=0 #表示隊(duì)列頭部位置
    def enqueue(self, item):
        self.entries.append(item) #添加元素到隊(duì)列里面
        self.length = self.length + 1 #隊(duì)列長(zhǎng)度增加 1
    def dequeue(self):
        self.length = self.length - 1 #隊(duì)列的長(zhǎng)度減少 1
        dequeued = self.entries[self.front] #隊(duì)首元素為dequeued
        self.front-=1 #隊(duì)首的位置減少1
        self.entries = self.entries[self.front:] #隊(duì)列的元素更新為退隊(duì)之后的隊(duì)列
        return dequeued
    def peek(self):
        return self.entries[0] #直接返回隊(duì)列的隊(duì)首元素

          
        

二叉樹(shù)

          
            class Node(object):
    def __init__(self,item):
        self.item=item #表示對(duì)應(yīng)的元素
        self.left=None #表示左節(jié)點(diǎn)
        self.right=None #表示右節(jié)點(diǎn)
    def __str__(self):
        return str(self.item)  #print 一個(gè) Node 類(lèi)時(shí)會(huì)打印 __str__ 的返回值
class Tree(object):
    def __init__(self):
        self.root=Node('root')  #根節(jié)點(diǎn)定義為 root 永不刪除，作為哨兵使用。
    def add(self,item):
        node = Node(item)
        if self.root is None:  #如果二叉樹(shù)為空，那么生成的二叉樹(shù)最終為新插入樹(shù)的點(diǎn)
            self.root = node
        else:
            q = [self.root] # 將q列表，添加二叉樹(shù)的根節(jié)點(diǎn)
            while True:
                pop_node = q.pop(0)
                if pop_node.left is None: #左子樹(shù)為空則將點(diǎn)添加到左子樹(shù)
                    pop_node.left = node
                    return
                elif pop_node.right is None: #右子樹(shù)為空則將點(diǎn)添加到右子樹(shù)
                    pop_node.right = node
                    return
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)
    def get_parent(self, item):
        if self.root.item == item:
            return None  # 根節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)
        tmp = [self.root] # 將tmp列表，添加二叉樹(shù)的根節(jié)點(diǎn)
        while tmp:
            pop_node = tmp.pop(0)
            if pop_node.left and pop_node.left.item == item: #某點(diǎn)的左子樹(shù)為尋找的點(diǎn)
                return pop_node #返回某點(diǎn)，即為尋找點(diǎn)的父節(jié)點(diǎn)
            if pop_node.right and pop_node.right.item == item: #某點(diǎn)的右子樹(shù)為尋找的點(diǎn)
                return pop_node #返回某點(diǎn)，即為尋找點(diǎn)的父節(jié)點(diǎn)
            if pop_node.left is not None: #添加tmp 元素
                tmp.append(pop_node.left)
            if pop_node.right is not None:
                tmp.append(pop_node.right)
        return None
    def delete(self, item):
        if self.root is None:  # 如果根為空，就什么也不做
            return False

        parent = self.get_parent(item)
        if parent:
            del_node = parent.left if parent.left.item == item else parent.right  # 待刪除節(jié)點(diǎn)
            if del_node.left is None:
                if parent.left.item == item:
                    parent.left = del_node.right
                else:
                    parent.right = del_node.right
                del del_node
                return True
            elif del_node.right is None:
                if parent.left.item == item:
                    parent.left = del_node.left
                else:
                    parent.right = del_node.left
                del del_node
                return True
            else:  # 左右子樹(shù)都不為空
                tmp_pre = del_node
                tmp_next = del_node.right
                if tmp_next.left is None:
                    # 替代
                    tmp_pre.right = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right

                else:
                    while tmp_next.left:  # 讓tmp指向右子樹(shù)的最后一個(gè)葉子
                        tmp_pre = tmp_next
                        tmp_next = tmp_next.left
                    # 替代
                    tmp_pre.left = tmp_next.right
                    tmp_next.left = del_node.left
                    tmp_next.right = del_node.right
                if parent.left.item == item:
                    parent.left = tmp_next
                else:
                    parent.right = tmp_next
                del del_node
                return True
        else:
            return False
          
        

字典樹(shù)

          
            class TrieNode:
    def __init__(self):
        self.nodes = dict()  # 構(gòu)建字典
        self.is_leaf = False
    def insert(self, word: str):  
        curr = self
        for char in word:
            if char not in curr.nodes:
                curr.nodes[char] = TrieNode()
            curr = curr.nodes[char]
        curr.is_leaf = True
    def insert_many(self, words: [str]):
        for word in words:
            self.insert(word)
    def search(self, word: str):
        curr = self
        for char in word:
            if char not in curr.nodes:
                return False
            curr = curr.nodes[char]
        return curr.is_leaf

          
        

堆

          
            class heap(object):
    def __init__(self):
        #初始化一個(gè)空堆，使用數(shù)組來(lái)在存放堆元素，節(jié)省存儲(chǔ)
        self.data_list = []
    def get_parent_index(self,index):
        #返回父節(jié)點(diǎn)的下標(biāo)
        if index == 0 or index > len(self.data_list) -1:
            return None
        else:
            return (index -1) >> 1
    def swap(self,index_a,index_b):
        #交換數(shù)組中的兩個(gè)元素
        self.data_list[index_a],self.data_list[index_b] = self.data_list[index_b],self.data_list[index_a]
    def insert(self,data):
        #先把元素放在最后，然后從后往前依次堆化
        #這里以大頂堆為例，如果插入元素比父節(jié)點(diǎn)大，則交換，直到最后
        self.data_list.append(data)
        index = len(self.data_list) -1 
        parent = self.get_parent_index(index)
        #循環(huán)，直到該元素成為堆頂，或小于父節(jié)點(diǎn)（對(duì)于大頂堆) 
        while parent is not None and self.data_list[parent] < self.data_list[index]:
            #交換操作
            self.swap(parent,index)
            index = parent
            parent = self.get_parent_index(parent)
    def removeMax(self):
        #刪除堆頂元素，然后將最后一個(gè)元素放在堆頂，再?gòu)纳贤乱来味鸦?        remove_data = self.data_list[0]
        self.data_list[0] = self.data_list[-1]
        del self.data_list[-1]

        #堆化
        self.heapify(0)
        return remove_data
    def heapify(self,index):
        #從上往下堆化，從index 開(kāi)始堆化操作 (大頂堆)
        total_index = len(self.data_list) -1
        while True:
            maxvalue_index = index
            if 2*index +1 <=  total_index and self.data_list[2*index +1] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index +1
            if 2*index +2 <=  total_index and self.data_list[2*index +2] > self.data_list[maxvalue_index]:
                maxvalue_index = 2*index +2
            if maxvalue_index == index:
                break
            self.swap(index,maxvalue_index)
            index = maxvalue_index
          
        

以上內(nèi)容僅介紹了常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的 Python 實(shí)現(xiàn)，更多的其他數(shù)據(jù)結(jié)構(gòu)可以前往實(shí)驗(yàn)樓學(xué)習(xí)完整課程內(nèi)容：《Python 實(shí)現(xiàn)各種常見(jiàn)算法》