基礎資料結構例：堆疊、佇列、鏈表、資料、字典、樹、等-有解無憂

堆疊 stack

堆疊（stack）又名堆疊，它是一種運算受限的線性表，限定僅在表尾進行插入和洗掉操作的線性表，這一端被稱為堆疊頂，把另一端稱為堆疊底，向一個堆疊插入新元素又稱作進堆疊、入堆疊或壓堆疊，它是把新元素放到堆疊頂元素的上面，使之成為新的堆疊頂元素；從一個堆疊洗掉元素又稱作出堆疊或退堆疊，它是把堆疊頂元素洗掉掉，使其相鄰的元素成為新的堆疊頂元素，堆疊作為一種資料結構，是一種只能在一端進行插入和洗掉操作的特殊線性表，它按照先進后出的原則存盤資料，先進入的資料被壓入堆疊底，最后的資料在堆疊頂，需要讀資料的時候從堆疊頂開始彈出資料（最后一個資料被第一個讀出來），堆疊具有記憶作用，對堆疊的插入與洗掉操作中，不需要改變堆疊底指標，堆疊是允許在同一端進行插入和洗掉操作的特殊線性表，允許進行插入和洗掉操作的一端稱為堆疊頂(top)，另一端為堆疊底(bottom)；堆疊底固定，而堆疊頂浮動；堆疊中元素個數為零時稱為空堆疊，插入一般稱為進堆疊（PUSH），洗掉則稱為退堆疊（POP），堆疊也稱為先進后出表，

堆疊可以用來在函式呼叫的時候存盤斷點，做遞回時要用到堆疊！

堆疊的特點：

后進先出，最后插入的元素最先出來，

Python實作

# 堆疊的順序表實作

class Stack(object):
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

def push(self, item):
return self.items.append(item)

def pop(self):
return self.items.pop()

def top(self):
return self.items[len(self.items)-1]

def size(self):
return len(self.items)

if __name__ == '__main__':
stack = Stack()
stack.push("Hello")
stack.push("World")
stack.push("!")
print(stack.size())
print(stack.top())
print(stack.pop())
print(stack.pop())
print(stack.pop())

# 結果
3
!
!
World
Hello

# 堆疊的鏈接表實作

class SingleNode(object):
def __init__(self, item):
self.item = item
self.next = None

class Stack(object):
def __init__(self):
self._head = None

def isEmpty(self):
return self._head == None

def push(self, item):
node = SingleNode(item)
node.next = self._head
self._head = node

def pop(self):
cur = self._head
self._head = cur.next
return cur.item

def top(self):
return self._head.item

def size(self):
cur = self._head
count = 0
while cur != None:
count += 1
cur = cur.next
return count

if __name__ == '__main__':
stack = Stack()
stack.push("Hello")
stack.push("World")
stack.push("!")
print(stack.size())
print(stack.top())
print(stack.pop())
print(stack.pop())
print(stack.pop())

# 結果
3
!
!
World
Hello

佇列

佇列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行洗掉操作，而在表的后端（rear）進行插入操作，和堆疊一樣，佇列是一種操作受限制的線性表，進行插入操作的端稱為隊尾，進行洗掉操作的端稱為隊頭，佇列中沒有元素時，稱為空佇列，

佇列的資料元素又稱為佇列元素，在佇列中插入一個佇列元素稱為入隊，從佇列中洗掉一個佇列元素稱為出隊，因為佇列只允許在一端插入，在另一端洗掉，所以只有最早進入佇列的元素才能最先從佇列中洗掉，故佇列又稱為先進先出（FIFO—first in first out）線性表.

佇列的特點：

先進者先出，最先插入的元素最先出來，
我們可以想象成，排隊買票，先來的先買，后來的只能在末尾，不允許插隊，

佇列的兩個基本操作：入隊將一個資料放到佇列尾部；出隊從佇列的頭部取出一個元素，佇列也是一種操作受限的線性表資料結構它具有先進先出的特性，支持隊尾插入元素，在隊頭洗掉元素，

佇列的概念很好理解，佇列的應用也非常廣泛如：回圈佇列、阻塞佇列、并發佇列、優先級隊列等，下面將會介紹，

順序佇列：
順序佇列就是我們常說的 “FIFO”（先進先出）佇列，它主要包括的方法有：取第一個元素（first方法）、進入佇列（enqueue方法）、出佇列（dequeue方法）、清空佇列（clear方法）、判斷佇列是否為空（empty方法）、獲取佇列長度（length方法），具體的實作看下面的源代碼，同樣，這里在取佇列的第一個元素、以及出佇列的時候，也需要判斷下佇列是否為空，

class Queue:
"""
順序佇列實作
"""

def __init__(self):
"""
初始化一個空佇列，因為佇列是私有的
"""
self.__queue = []

def first(self):
"""
獲取佇列的第一個元素
:return:如果佇列為空，則回傳None，否則回傳第一個元素
"""
return None if self.isEmpty() else self.__queue[0]

def enqueue(self, obj):
"""
將元素加入佇列
:param obj:要加入佇列的物件
"""
self.__queue.append(obj)

def dequeue(self):
"""
從佇列中洗掉第一個元素
:return:如果佇列為空，則回傳None，否則回傳dequeued元素
"""
return None if self.isEmpty() else self.__queue.pop(0)

def clear(self):
"""
清除整個佇列
"""
self.__queue.clear()

def isEmpty(self):
"""
判斷佇列是否為空
回傳:bool值
"""
return self.length() == 0

def length(self):
"""
獲取佇列長度
并回傳
"""
return len(self.__queue)

優先佇列：
優先佇列簡單說就是一個有序佇列，排序的規則就是自定義的優先級大小，在下面的代碼實作中，主要使用的是數值大小進行比較排序，數值越小則優先級越高，理論上應該把優先級高的放在佇列首位，值得注意的是，筆者這里用list來實作的時候恰好順序是反的，即list中元素是從大到小的順序，這樣做的好處是取佇列的第一個元素、以及出佇列這兩個操作的時間復雜度為O(1)，僅僅入佇列操作的時間復雜度為O(n)，如果是按照從小到大的順序，那么將會產生兩個時間復雜度為O(n)，一個時間復雜度為O(1)，

class PriorQueue:
"""
優先佇列實作
"""

def __init__(self, objs=[]):
"""
初始化優先佇列，默認佇列為空
:引數objs:物件串列初始化
"""
self.__prior_queue = list(objs)
# 排序從最大值到最小值，最小值具有最高的優先級
# 使得“dequeue”的效率為O(1)
self.__prior_queue.sort(reverse=True)

def first(self):
"""
獲取優先佇列的最高優先級元素O(1)
:return:如果優先佇列為空，則回傳None，否則回傳優先級最高的元素
"""
return None if self.isEmpty() else self.__prior_queue[-1]

def enqueue(self, obj):
"""
將一個元素加入優先佇列，O(n)
:param obj:要加入佇列的物件
"""
index = self.length()
while index > 0:
if self.__prior_queue[index - 1] < obj:
index -= 1
else:
break
self.__prior_queue.insert(index, obj)

def dequeue(self):
"""
從優先佇列中取出最高優先級的元素，O(1)
:return:如果優先佇列為空，則回傳None，否則回傳dequeued元素
"""
return None if self.isEmpty() else self.__prior_queue.pop()

def clear(self):
"""
清除整個優先佇列
"""
self.__prior_queue.clear()

def isEmpty(self):
"""
判斷優先佇列是否為空
回傳:bool值
"""
return self.length() == 0

def length(self):
"""
獲取優先佇列的長度
回傳:
"""
return len(self.__prior_queue)

回圈佇列：
回圈佇列，就是將普通的佇列首尾連接起來，形成一個環狀，并分別設定首尾指標，用來指明佇列的頭和尾，每當我們插入一個元素，尾指標就向后移動一位，當然，在這里我們佇列的最大長度是提前定義好的，當我們彈出一個元素，頭指標就向后移動一位，

這樣，串列中就不存在洗掉操作，只有修改操作，從而避免了洗掉前面節點造成的代價大的問題，

class Loopqueue:
'''
回圈佇列實作
'''
def __init__(self, length):
self.head = 0
self.tail = 0
self.maxSize = length
self.cnt = 0
self.__list = [None]*length

def __len__(self):
'''
定義長度
'''
return self.cnt

def __str__(self):
'''
定義回傳值 型別
'''
s = ''
for i in range(self.cnt):
index = (i + self.head) % self.maxSize
s += str(self.__list[index])+' '
return s

def isEmpty(self):
'''
判斷是否為空
'''
return self.cnt == 0

def isFull(self):
'''
判斷是否裝滿
'''
return self.cnt == self.maxSize

def push(self, data):
'''
添加元素
'''
if self.isFull():
return False
if self.isEmpty():
self.__list[0] = data
self.head = 0
self.tail = 0
self.cnt = 1
return True
self.tail = (self.tail+1)%self.maxSize
self.cnt += 1
self.__list[self.tail] = data
return True

def pop(self):
'''
彈出元素
'''
if self.isEmpty():
return False
data = self.__list[self.head]
self.head = (self.head+1)%self.maxSize
self.cnt -= 1
return data

def clear(self):
'''
清空佇列
'''
self.head = 0
self.tail = 0
self.cnt = 0
return True

阻塞佇列
阻塞佇列是一個在佇列基礎上又支持了兩個附加操作的佇列，

阻塞（并發）佇列與普通佇列的區別在于，當佇列是空的時，從佇列中獲取元素的操作將會被阻塞，或者當佇列是滿時，往佇列里添加元素的操作會被阻塞，試圖從空的阻塞佇列中獲取元素的執行緒將會被阻塞，直到其他的執行緒往空的佇列插入新的元素，同樣，試圖往已滿的阻塞佇列中添加新元素的執行緒同樣也會被阻塞，直到其他的執行緒使佇列重新變得空閑起來，如從佇列中移除一個或者多個元素，或者完全清空佇列.

2個附加操作：
支持阻塞的插入方法：佇列滿時，佇列會阻塞插入元素的執行緒，直到佇列不滿，
支持阻塞的移除方法：佇列空時，獲取元素的執行緒會等待佇列變為非空，

怎么實作阻塞佇列？當然是靠鎖，但是應該怎么鎖？一把鎖能在not_empty，not_full，all_tasks_done三個條件之間共享，好比說，現在有執行緒A執行緒B，他們準備向佇列put任務，佇列的最大長度是5，執行緒A在put時，還沒完事，執行緒B就開始put，佇列就塞不下了，所以當執行緒A搶占到put權時應該加把鎖，不讓執行緒B對佇列操作，鬼畜區經常看到的計資料，在執行緒中也同樣重要，每次put完unfinished要加一，get完unfinished要減一，

import threading #引入執行緒 上鎖
import time
from collections import deque # 匯入佇列


class BlockQueue:
def __init__(self, maxsize=0):
'''
一把鎖三個條件（self.mutex,(self.not_full, self.not_empty, self.all_task_done)）,
最大長度與計資料（self.maxsize,self.unfinished）
'''
self.mutex = threading.Lock() # 執行緒上鎖
self.maxsize = maxsize 
self.not_full = threading.Condition(self.mutex)
self.not_empty = threading.Condition(self.mutex)
self.all_task_done = threading.Condition(self.mutex)
self.unfinished = 0

def task_done(self):
'''
每一次put完都會呼叫一次task_done，而且呼叫的次數不能比佇列的元素多，計資料對應的方法，
unfinished<0時的意思是呼叫task_done的次數比串列的元素多，這種情況就會拋出例外，
'''
with self.all_task_done:
unfinish = self.unfinished - 1
if unfinish <= 0:
if unfinish < 0:
raise ValueError("The number of calls to task_done() is greater than the number of queue elements")
self.all_task_done.notify_all()
self.unfinished = unfinish

def join(self):
'''
阻塞方法，是一個十分重要的方法，但它的實作也不難，只要沒有完成任務就一直wait（），
就是當計資料unfinished > 0 時就一直wait（）知道unfinished=0跳出回圈，
'''
with self.all_task_done:
while self.unfinished:
self.all_task_done.wait()

def put(self, item, block=True, timeout=None):
'''
block=True一直阻塞直到有一個空閑的插槽可用，n秒內阻塞，如果在那個時間沒有空閑的插槽，則會引發完全的例外，
Block=False如果一個空閑的槽立即可用，則在佇列上放置一個條目，否則就會引發完全的例外（在這種情況下，“超時”將被忽略），
有空位，添加到佇列沒結束的任務+1，他最后要喚醒not_empty.notify()，因為一開始是要在沒滿的情況下加鎖，滿了就等待not_full.wait,
當put完以后就有東西了，每當一個item被添加到佇列時，通知not_empty等待獲取的執行緒會被通知，
'''
with self.not_full:
if self.maxsize > 0:
if not block:
if self._size() >= self.maxsize:
raise Exception("The BlockQueue is full")
elif timeout is not None:
self.not_full.wait()
elif timeout < 0:
raise Exception("The timeout period cannot be negative")
else:
endtime = time.time() + timeout
while self._size() >= self.maxsize:
remaining = endtime - time.time()
if remaining <= 0.0:
raise Exception("The BlockQueue is full")
self.not_full.wait(remaining)
self.queue.append(item)
self.unfinished += 1
self.not_empty.notify()

def get(self, block=True, timeout=None):
'''
如果可選的args“block”為True，并且timeout是None，則在必要時阻塞，直到有一個專案可用為止，
如果“超時”是一個非負數，它會阻塞n秒，如果在那個時間內沒有可get（）的項，則會拋出空例外，
否則'block'是False，如果立即可用，否則就會拋出空例外，在這種情況下會忽略超時，
同理要喚醒not_full.notify
'''
with self.not_empty:
if not block:
if self._size() <= 0:
raise Exception("The queue is empty and you can't call get ()")
elif timeout is None:
while not self._size():
self.not_empty.wait()
elif timeout < 0:
raise ValueError("The timeout cannot be an integer")
else:
endtime = time.time() + timeout
remaining = endtime - time.time()
if remaining <= 0.0:
raise Exception("The BlockQueue is empty")
self.not_empty.wait(remaining)
item = self._get()
self.not_full.notify()
return item

并發佇列:
在并發佇列上JDK提供了兩套實作，

一個是以ConcurrentLinkedQueue為代表的高性能佇列非阻塞，

一個是以BlockingQueue介面為代表的阻塞佇列，無論哪種都繼承自Queue，

鏈式佇列：
鏈式佇列在創建一個佇列時，隊頭指標front和隊尾指標rear指向結點的data域和next域均為空，

class QueueNode():
def __init__(self):
self.data = None
self.next = None
class LinkQueue():
def __init__(self):
tQueueNode = QueueNode()
self.front = tQueueNode
self.rear = tQueueNode
'''判斷是否為空'''
def IsEmptyQueue(self):
if self.front == self.rear:
iQueue = True
else:
iQueue = False
return iQueue
'''進佇列'''
def EnQueue(self,da):
tQueueNode = QueueNode()
tQueueNode.data = da
self.rear.next = tQueueNode
self.rear = tQueueNode
print("當前進隊的元素為：",da)
'''出佇列'''
def DeQueue(self):
if self.IsEmptyQueue():
print("佇列為空")
return
else:
tQueueNode = self.front.next
self.front.next = tQueueNode.next
if self.rear == tQueueNode:
self.rear = self.front
return tQueueNode.data
def GetHead(self):
if self.IsEmptyQueue():
print("佇列為空")
return
else:
return self.front.next.data
def CreateQueueByInput(self):
data = input("請輸入元素（回車鍵確定，#結束）")
while data != "#":
self.EnQueue(data)
data = input("請輸入元素（回車鍵確定，#結束）")
'''遍歷順序佇列內的所有元素'''
def QueueTraverse(self):
if self.IsEmptyQueue():
print("佇列為空")
return
else:
while self.front != self.rear:
result = self.DeQueue()
print(result,end = ' ')
lq = LinkQueue()
lq.CreateQueueByInput()
print("佇列里元素為：")
lq.QueueTraverse()

# 結果

請輸入元素（回車鍵確定，#結束）5
當前進隊的元素為：5
請輸入元素（回車鍵確定，#結束）8
當前進隊的元素為：8
請輸入元素（回車鍵確定，#結束）9
當前進隊的元素為：9
請輸入元素（回車鍵確定，#結束）#
佇列的元素為：
5 8 9

鏈表

鏈表是一種物理存盤單元上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成，每個結點包括兩個部分：一個是存盤資料元素的資料域，另一個是存盤下一個結點地址的指標域，相比于線性表順序結構，操作復雜，由于不必須按順序存盤，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)，

鏈表是一種物理存盤結構上非連續，非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，

鏈表的結構是多式多樣的，當時通常用的也就是兩種：

無頭單向非回圈串列：結構簡單，一般不會單獨用來存放資料，實際中更多是作為其他資料結構的子結構，比如說哈希桶等等，
??帶頭雙向回圈鏈表：結構最復雜，一般單獨存盤資料，實際中經常使用的鏈表資料結構，都是帶頭雙向回圈鏈表，這個結構雖然復雜，但是使用代碼實作后會發現這個結構會帶來很多優勢，實作反而簡單了，

鏈表的優點
插入和洗掉的效率高，只需要改變指標的指向就可以進行插入和洗掉，
記憶體利用率高，不會浪費記憶體，可以使用記憶體中細小的不連續的空間，只有在需要的時候才去創建空間，大小不固定，拓展很靈活，

鏈表的缺點
查找的效率低，因為鏈表是從第一個節點向后遍歷查找，

單向鏈表
單向鏈表（單鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始；鏈表是使用指標進行構造的串列；又稱為結點串列，因為鏈表是由一個個結點組裝起來的；其中每個結點都有指標成員變數指向串列中的下一個結點；串列是由結點構成，head指標指向第一個成為表頭結點，而終止于最后一個指向NULL的指標，

單鏈表的每一個節點中只有指向下一個結點的指標，不能進行回溯，適用于節點的增加和洗掉，

class Node(object):
"""節點"""

def __init__(self, elem):
self.elem = elem
self.next = None # 初始設定下一節點為空

'''
上面定義了一個節點的類，當然也可以直接使用python的一些結構，比如通過元組（elem, None）
'''


# 下面創建單鏈表，并實作其應有的功能


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

def __init__(self, node=None): # 使用一個默認引數，在傳入頭結點時則接收，在沒有傳入時，就默認頭結點為空
self.__head = node

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

def length(self):
'''鏈表長度'''
# cur游標，用來移動遍歷節點
cur = self.__head
# count記錄數量
count = 0
while cur != None:
count += 1
cur = cur.next
return count

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

def remove(self, item):
'''洗掉節點'''
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
# 先判斷該節點是否是頭結點
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next

def search(self, item):
'''查找節點是否存在'''
cur = self.__head
while not cur:
if cur.elem == item:
return True
else:
cur = cur.next
return False


if __name__ == "__main__":

# node = Node(100) # 先創建一個節點傳進去

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()

雙向鏈表
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個資料結點中都有兩個指標，分別指向直接后繼和直接前驅，所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點，一般我們都構造雙向回圈鏈表，

雙鏈表的每一個節點給中既有指向下一個結點的指標，也有指向上一個結點的指標，可以快速的找到當前節點的前一個節點，適用于需要雙向查找節點值的情況，

和單鏈表類似，只不過是增加了一個指向前面一個元素的指標而已，

class Node(object):
def __init__(self,val,p=0):
self.data = val
self.next = p
self.prev = p

class LinkList(object):
def __init__(self):
self.head = 0

def __getitem__(self, key):

if self.is_empty():
print 'linklist is empty.'
return

elif key <0 or key > self.getlength():
print 'the given key is error'
return

else:
return self.getitem(key)

 

def __setitem__(self, key, value):

if self.is_empty():
print 'linklist is empty.'
return

elif key <0 or key > self.getlength():
print 'the given key is error'
return

else:
self.delete(key)
return self.insert(key)

def initlist(self,data):

self.head = Node(data[0])

p = self.head

for i in data[1:]:
node = Node(i)
p.next = node
node.prev = p
p = p.next

def getlength(self):

p = self.head
length = 0
while p!=0:
length+=1
p = p.next

return length

def is_empty(self):

if self.getlength() ==0:
return True
else:
return False

def clear(self):

self.head = 0


def append(self,item):

q = Node(item)
if self.head ==0:
self.head = q
else:
p = self.head
while p.next!=0:
p = p.next
p.next = q
q.prev = p


def getitem(self,index):

if self.is_empty():
print 'Linklist is empty.'
return
j = 0
p = self.head

while p.next!=0 and j <index:
p = p.next
j+=1

if j ==index:
return p.data

else:

print 'target is not exist!'

def insert(self,index,item):

if self.is_empty() or index<0 or index >self.getlength():
print 'Linklist is empty.'
return

if index ==0:
q = Node(item,self.head)

self.head = q

p = self.head
post = self.head
j = 0
while p.next!=0 and j<index:
post = p
p = p.next
j+=1

if index ==j:
q = Node(item,p)
post.next = q
q.prev = post
q.next = p
p.prev = q


def delete(self,index):

if self.is_empty() or index<0 or index >self.getlength():
print 'Linklist is empty.'
return

if index ==0:
q = Node(item,self.head)

self.head = q

p = self.head
post = self.head
j = 0
while p.next!=0 and j<index:
post = p
p = p.next
j+=1

if index ==j:
post.next = p.next
p.next.prev = post

def index(self,value):

if self.is_empty():
print 'Linklist is empty.'
return

p = self.head
i = 0
while p.next!=0 and not p.data =https://www.cnblogs.com/yangmaosen/p/=value:
p = p.next
i+=1

if p.data =https://www.cnblogs.com/yangmaosen/p/= value:
return i
else:
return -1


l = LinkList()
l.initlist([1,2,3,4,5])
print l.getitem(4)
l.append(6)
print l.getitem(5)

l.insert(4,40)
print l.getitem(3)
print l.getitem(4)
print l.getitem(5)

l.delete(5)
print l.getitem(5)

l.index(5)

# 結果
5
6
4
40
5
6

雙鏈表相對于單鏈表的優點：

洗掉單鏈表中的某個節點時，一定要得到待洗掉節點的前驅，得到其前驅的方法一般是在定位待洗掉節點的時候一路保存當前節點的前驅，這樣指標的總的的移動操作為2n次，如果是用雙鏈表，就不需要去定位前驅，所以指標的總的的移動操作為n次，
??查找時也是一樣的，可以用二分法的思路，從頭節點向后和尾節點向前同時進行，這樣效率也可以提高一倍，但是為什么市場上對于單鏈表的使用要超過雙鏈表呢？從存盤結構來看，每一個雙鏈表的節點都比單鏈表的節點多一個指標，如果長度是n，就需要n*lenght（32位是4位元組，64位是8位元組）的空間，這在一些追求時間效率不高的應用下就不適用了，因為他占的空間大于單鏈表的1/3，所以設計者就會一時間換空間，

單向鏈表的反轉
名如其意：將單鏈表進行反轉，
舉例：將 1234 反轉為 4321 怎么操作
1234->2134->2314->2341->3241->3421->4321,這樣也太費勁了，類似冒泡排序了
應該是每次把n后面的數字放到前面來，1234n->1n234->21n34->321n4->4321n

那么接下來用 Python 實作

第一種方法 回圈方法
回圈方法的思想是建立三個變數，分別指向當前結點，當前結點的前一個結點，新的head結點，從head開始，每次回圈將相鄰兩個結點的方向反轉，當整個鏈表回圈遍歷過一遍之后，鏈表的方向就被反轉過來了，

class ListNode:
def __init__(self, x):
self.val = x
self.next = None


def reverse(head): # 回圈的方法反轉鏈表
if head is None or head.next is None:
return head
# 定義反轉的初始狀態
pre = None
cur = head
newhead = head
while cur:
newhead = cur
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return newhead

if __name__ == '__main__':
head = ListNode(1) # 測驗代碼
p1 = ListNode(2) # 建立鏈表1->2->3->4->None;
p2 = ListNode(3)
p3 = ListNode(4)
head.next = p1
p1.next = p2
p2.next = p3
p = reverse(head) # 輸出鏈表 4->3->2->1->None
while p:
print(p.val)
p = p.next

第二種呢就是 遞回方法

根據遞回的概念，我們只需要關注遞回的基例條件，也就是遞回的出口或遞回的終止條件，以及長度為n的鏈表與長度為n-1的鏈表的關系即可
長度為n的鏈表的反轉結果，只需要將長度為n-1的鏈表反轉后，將鏈表最后指向None修改為指向長度為n的鏈表的head，并讓head指向None（或者說在鏈表與None之間添加長度為n的鏈表的head結點）
即反轉長度為n的鏈表，首先反轉n-1鏈表，然后再操作反轉好的鏈表與head結點的關系；至于n-1長度的鏈表怎么反轉，只需要把它再拆分成node1和n-2的鏈表…

class ListNode:
def __init__(self, x):
self.val = x
self.next = None


def reverse(head, newhead): # 遞回，head為原鏈表的頭結點，newhead為反轉后鏈表的頭結點
if head is None:
return
if head.next is None:
newhead = head
else:
newhead = reverse(head.next, newhead)
head.next.next = head
head.next = None
return newhead

if __name__ == '__main__':
head = ListNode(1) # 測驗代碼
p1 = ListNode(2) # 建立鏈表1->2->3->4->None
p2 = ListNode(3)
p3 = ListNode(4)
head.next = p1
p1.next = p2
p2.next = p3
newhead = None
p = reverse(head, newhead) # 輸出鏈表4->3->2->1->None
while p:
print(p.val)
p = p.next

陣列

所謂陣列，是有序的元素序列，若將有限個型別相同的變數的集合命名，那么這個名稱為陣列名，組成陣列的各個變數稱為陣列的分量，也稱為陣列的元素，有時也稱為下標變數，用于區分陣列的各個元素的數字編號稱為下標，陣列是在程式設計中，為了處理方便，把具有相同型別的若干元素按無序的形式組織起來的一種形式，這些無序排列的同類資料元素的集合稱為陣列，
陣列是用于儲存多個相同型別資料的集合，

Python 沒有內置對陣列的支持，但可以使用 Python 串列代替，

一維陣列
一維陣列是最簡單的陣列，其邏輯結構是線性表，要使用一維陣列，需經過定義、初始化和應用等程序，

在陣列的宣告格式里，“資料型別”是宣告陣列元素的資料型別，可以是java語言中任意的資料型別，包括簡單型別和結構型別，“陣列名”是用來統一這些相同資料型別的名稱，其命名規則和變數的命名規則相同，
陣列宣告之后，接下來便是要分配陣列所需要的記憶體，這時必須用運算子new，其中“個數”是告訴編譯器，所宣告的陣列要存放多少個元素，所以new運算子是通知編譯器根據括號里的個數，在記憶體中分配一塊空間供該陣列使用，利用new運算子為陣列元素分配記憶體空間的方式稱為動態分配方式，

二維陣列
前面介紹的陣列只有一個下標，稱為一維陣列，其陣列元素也稱為單下標變數，在實際問題中有很多量是二維的或多維的，因此多維陣列元素有多個下標，以標識它在陣列中的位置，所以也稱為多下標變數，

二維陣列在概念上是二維的，即是說其下標在兩個方向上變化，下標變數在陣列中的位置也處于一個平面之中，而不是象一維陣列只是一個向量，但是，實際的硬體存盤器卻是連續編址的，也就是說存盤器單元是按一維線性排列的，如何在一維存盤器中存放二維陣列，可有兩種方式：一種是按行排列，即放完一行之后順次放入第二行，另一種是按列排列，即放完一列之后再順次放入第二列，在C語言中，二維陣列是按行排列的，在如上中，按行順次存放，先存放a[0]行，再存放a[1]行，最后存放a[2]行，每行中有四個元素也是依次存放，由于陣列a說明為
int型別，該型別占兩個位元組的記憶體空間，所以每個元素均占有兩個位元組（圖中每一格為一位元組），

三維陣列
三維陣列，是指維數為三的陣列結構，三維陣列是最常見的多維陣列，由于其可以用來描述三維空間中的位置或狀態而被廣泛使用，
三維陣列就是維度為三的陣列，可以認為它表示對該陣列存盤的內容使用了三個獨立參量去描述，但更多的是認為該陣列的下標是由三個不同的參量組成的，
陣列這一概念主要用在撰寫程式當中，和數學中的向量、矩陣等概念有一定的差別，主要表現：在陣列內的元素可以是任意的相同資料型別，包括向量和矩陣，
對陣列的訪問一般是通過下標進行的，在三維陣列中，陣列的下標是由三個數字構成的，通過這三個數字組成的下標對陣列的內容進行訪問，

字符陣列
用來存放字符量的陣列稱為字符陣列，
字符陣列型別說明的形式與前面介紹的數值陣列相同，例如：char c[10]; 由于字符型和整型通用，也可以定義為int c[10]但這時每個陣列元素占2個位元組的記憶體單元，
字符陣列也可以是二維或多維陣列，例如：char c[5][10]；即為二維字符陣列

字典實作原理 NSDictionary

Python 中 dict 物件是表明了其是一個原始的Python資料型別，按照鍵值對的方式存盤，其中文名字翻譯為字典，顧名思義其通過鍵名查找對應的值會有很高的效率，時間復雜度在常數級別O(1)

dict底層實作
在Python中，字典是通過哈希表實作的，也就是說，字典是一個陣列，而陣列的索引是鍵經過哈希函式處理后得到的，

哈希表
是根據關鍵碼值(Key value)而直接進行訪問的資料結構，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度，
這個映射函式叫做散列函式，存放記錄的陣列叫做散串列，
給定表M，存在函式f(key)，對任意給定的關鍵字值key，代入函式后若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表.
函式f(key)為哈希(Hash) 函式，

>>> map(hash, (0, 1, 2, 3)) 

[0, 1, 2, 3] 

>>> map(hash, ("namea", "nameb", "namec", "named")) 

[-1658398457, -1658398460, -1658398459, -1658398462]

哈希概念:哈希表的本質是一個陣列，陣列中每一個元素稱為一個箱子(bin)，箱子中存放的是鍵值對，

哈希函式
哈希函式就是一個映射，因此哈希函式的設定很靈活，只要使得任何關鍵字由此所得的哈希函式值都落在表長允許的范圍之內即可；
并不是所有的輸入都只對應唯一一個輸出，也就是哈希函式不可能做成一個一對一的映射關系，其本質是一個多對一的映射，這也就引出了下面一個概念–沖突，

沖突

只要不是一對一的映射關系，沖突就必然會發生，還是上面的極端例子，這時新加了一個員工號為2的員工，先不考慮我們的陣列大小已經定為2了，按照之前的哈希函式，工號為2的員工哈希值也是2，這與100000000001的員工一樣了，這就是一個沖突，針對不同的解決思路，提出三個不同的解決方法，

沖突解決方法

開放地址
開放地址的意思是除了哈希函式得出的地址可用，當出現沖突的時候其他的地址也一樣可用，常見的開放地址思想的方法有線性探測再散列，二次探測再散列，這些方法都是在第一選擇被占用的情況下的解決方法，

再哈希法
這個方法是按順序規定多個哈希函式，每次查詢的時候按順序呼叫哈希函式，呼叫到第一個為空的時候回傳不存在，呼叫到此鍵的時候回傳其值，

鏈地址法
將所有關鍵字哈希值相同的記錄都存在同一線性鏈表中，這樣不需要占用其他的哈希地址，相同的哈希值在一條鏈表上，按順序遍歷就可以找到，

公共溢位區
其基本思想是：所有關鍵字和基本表中關鍵字為相同哈希值的記錄，不管他們由哈希函式得到的哈希地址是什么，一旦發生沖突，都填入溢位表，

裝填因子α
一般情況下，處理沖突方法相同的哈希表，其平均查找長度依賴于哈希表的裝填因子，哈希表的裝填因子定義為表中填入的記錄數和哈希表長度的壁紙，也就是標志著哈希表的裝滿程度，直觀看來，α越小，發生沖突的可能性就越小，反之越大，一般0.75比較合適，涉及數學推導，

哈希存盤程序

1.根據 key 計算出它的哈希值 h，

2.假設箱子的個數為 n，那么這個鍵值對應該放在第 (h % n) 個箱子中，

3.如果該箱子中已經有了鍵值對，就使用開放尋址法或者拉鏈法解決沖突，

在使用拉鏈法解決哈希沖突時，每個箱子其實是一個鏈表，屬于同一個箱子的所有鍵值對都會排列在鏈表中，哈希表還有一個重要的屬性: 負載因子(load factor)，它用來衡量哈希表的空/滿程度，一定程度上也可以體現查詢的效率，計算公式為:負載因子 = 總鍵值對數 / 箱子個數負載因子越大，意味著哈希表越滿，越容易導致沖突，性能也就越低，因此，一般來說，當負載因子大于某個常數(可能是 1，或者 0.75 等)時，哈希表將自動擴容，哈希表在自動擴容時，一般會創建兩倍于原來個數的箱子，因此即使 key 的哈希值不變，對箱子個數取余的結果也會發生改變，因此所有鍵值對的存放位置都有可能發生改變，這個程序也稱為重哈希(rehash)，哈希表的擴容并不總是能夠有效解決負載因子過大的問題，假設所有 key 的哈希值都一樣，那么即使擴容以后他們的位置也不會變化，雖然負載因子會降低，但實際存盤在每個箱子中的鏈表長度并不發生改變，因此也就不能提高哈希表的查詢性能，基于以上總結，細心的朋友可能會發現哈希表的兩個問題:

1.如果哈希表中本來箱子就比較多，擴容時需要重新哈希并移動資料，性能影響較大，

2.如果哈希函式設計不合理，哈希表在極端情況下會變成線性表，性能極低，

Python中所有不可變的內置型別都是可哈希的，
可變型別（如串列，字典和集合）就是不可哈希的，因此不能作為字典的鍵，

樹

樹是一種資料結構，它是由n（n>=1）個有限結點組成一個具有層次關系的集合，把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，它具有以下的特點：
每個結點有零個或多個子結點；沒有父結點的結點稱為根結點；每一個非根結點有且只有一個父結點；除了根結點外，每個子結點可以分為多個不相交的子樹；

樹是一種重要的非線性資料結構，直觀地看，它是資料元素（在樹中稱為結點）按分支關系組織起來的結構，很象自然界中的樹那樣，

樹的定義：
樹是由邊連接的節點或頂點的分層集合，樹不能有回圈，并且只有節點和它的下降節點或子節點之間存在邊，同一父級的兩個子節點在它們之間不能有任何邊，每個節點可以有一個父節點除非是頂部節點，也稱為根節點，每棵樹只能有一個根節點，每個節點可以有零個或多個子節點，在下面的圖中，A是根節點，B、C和D是A的子節點，我們也可以說，A是B、C、D的父節點，B、C和D被稱為兄弟姐妹，因為它們是來自同一父節點A，

樹的種類：

無序樹：樹中任意節點的子結點之間沒有順序關系，這種樹稱為無序樹,也稱為自由樹;
有序樹：樹中任意節點的子結點之間有順序關系，這種樹稱為有序樹；
二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹；
完全二叉樹
滿二叉樹
哈夫曼樹：帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹；

樹的深度：

定義一棵樹的根結點層次為1，其他節點的層次是其父結點層次加1，一棵樹中所有結點的層次的最大值稱為這棵樹的深度，

二叉樹、滿二叉樹、完全二叉樹
二叉樹是一種特殊的樹：它或者為空，在二叉樹中每個節點最多有兩個子節點，一般稱為左子節點和右子節點（或左孩子和右孩子），并且二叉樹的子樹有左右之分，其次序不能任意顛倒，

滿二叉樹：在一棵二叉樹中，如果所有分支結點都有左孩子和右孩子結點，并且葉子結點都集中在二叉樹的最下層，這樣的樹叫做滿二叉樹

完全二叉樹：若二叉樹中最多只有最下面兩層的結點的度數可以小于2，并且最下面一層的葉子結點都是依次排列在該層最左邊的位置上，則稱為完全二叉樹

區別：滿二叉樹是完全二叉樹的特例，因為滿二叉樹已經滿了，而完全并不代表滿，所以形態你也應該想象出來了吧，滿指的是出了葉子節點外每個節點都有兩個孩子，而完全的含義則是最后一層沒有滿，并沒有滿，

二叉樹

在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構，通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree），二叉樹常被用于實作二叉查找樹和二叉堆，

二叉樹是遞回定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：

(1)空二叉樹——如圖(a)；
(2)只有一個根結點的二叉樹——如圖(b)；
(3)只有左子樹——如圖(1)；
(4)只有右子樹——如圖(3)；
(5)完全二叉樹——如圖(3)，

注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形， [1]

hash樹
哈希樹（或哈希特里）是一種持久性資料結構，可用于實作集合和映射，旨在替換純函式式編程中的哈希表，在其基本形式中，哈希樹在trie中存盤其鍵的哈希值（被視為位串），其中實際鍵和（可選）值存盤在trie的“最終”節點中

什么是質數：即只能被 1 和本身整除的數，

為什么用質數：因為N個不同的質數可以 ”辨別“ 的連續整數的數量，與這些質數的乘積相同，

也就是說如果有21億個數字的話，我們查找的哪怕是最底層的也僅僅需要計算10次就能找到對應的數字，
所以hash樹是一棵為查找而生的樹，

例如：
從2起的連續質數，連續10個質數就可以分辨大約M(10) =23571113171923*29= 6464693230 個數，已經超過計算機中常用整數（32bit）的表達范圍，連續100個質數就可以分辨大約M(100) = 4.711930 乘以10的219次方，
而按照目前的CPU水平，100次取余的整數除法操作幾乎不算什么難事，在實際應用中，整體的操作速度往往取決于節點將關鍵字裝載記憶體的次數和時間，一般來說，裝載的時間是由關鍵字的大小和硬體來決定的；在相同型別關鍵字和相同硬體條件下，實際的整體操作時間就主要取決于裝載的次數，他們之間是一個成正比的關系，