數組
數組的設計
數組設計之初是在形式上依賴內存分配而成的，所以必須在使用前預先請求空間。這讓陣列有以下特性：
1、請求空間以後大小固定，不能再改變（資料溢位問題）；
2、記憶體中有空間連續性的表現，而中間不會有其他程式需要呼叫的數據，為此數組的專用記憶體空間；
3、在舊式程式語言中（如有中階語言之稱的C），程式不會對數組的操作做下界判斷，也就有潛在的越界操作的風險（例如會把資料寫在運行中程式需要呼叫的核心部分的記憶體上）。
因為簡單數組強烈倚賴電腦硬體之內存，所以不適用於現代的程式設計。若要使用可變大小、硬體無關性的資料類型，Java等程式設計語言均提供了更進階的資料結構：ArrayList、Vector等動態陣列。
Python的陣列
從嚴格意義上來說:Python裡沒有嚴格意義上的陣列。
List可以說是Python裡的數組，下面這段程式碼是CPython的實作List的結構體:
typedef struct {
PyObject_VAR_HEAD
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for 'allocated' elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
* list.sort() temporarily sets allocated to -1 to detect mutations.
*
* Items must normally not be NULL, except during construction when
* the list is not yet visible outside the function that builds it.
*/
Py_ssize_t allocated;
} PyListObject;登入後複製
當然，在Python裡它就是數組。
後面的一些結構也會用List來實現。
堆疊
什麼是堆疊
堆疊（英文：stack），也可直接稱棧，在電腦科學中，是一種特殊的串列形式的資料結構在於只能允許在連結串列或陣列的一端（稱為堆疊頂端指標，英文：top）進行加入資料（英文：push）和輸出資料（英文：pop）的運算。另外堆疊也可以用一維陣列或連結串列的形式來完成。堆疊的另外一個相對的操作方式稱為佇列。
由於堆疊資料結構只允許在一端進行操作，因而按照後進先出（LIFO, Last In First Out）的原理運作。
特色
1.先入後出，後入先出。
2、除頭尾節點之外，每個元素都有一個前驅，一個後繼。
操作
從原理可知，對堆疊(棧)可以進行的操作有:
1、top() :獲取堆疊和堆疊物件
:p
3、pop() :從堆疊中推出一個物件
實作
class my_stack(object):
def __init__(self, value):
self.value = value
# 前驱
self.before = None
# 后继
self.behind = None
def __str__(self):
return str(self.value)
def top(stack):
if isinstance(stack, my_stack):
if stack.behind is not None:
return top(stack.behind)
else:
return stack
def push(stack, ele):
push_ele = my_stack(ele)
if isinstance(stack, my_stack):
stack_top = top(stack)
push_ele.before = stack_top
push_ele.before.behind = push_ele
else:
raise Exception('不要乱扔东西进来好么')
def pop(stack):
if isinstance(stack, my_stack):
stack_top = top(stack)
if stack_top.before is not None:
stack_top.before.behind = None
stack_top.behind = None
return stack_top
else:
print('已经是栈顶了')
登入後複製
佇列
什麼是佇列
所以隊列是先進先出（FIFO, First-In-First-Out）的線性表
特徵
1、先入先出,後入後出
節點
1、先入先出,後入後出對每個節點有後繼
3、（可選）除頭節點外,每個節點有一個前驅
操作
隊
實作
普通隊列
class MyQueue():
def __init__(self, value=None):
self.value = value
# 前驱
# self.before = None
# 后继
self.behind = None
def __str__(self):
if self.value is not None:
return str(self.value)
else:
return 'None'
def create_queue():
"""仅有队头"""
return MyQueue()
def last(queue):
if isinstance(queue, MyQueue):
if queue.behind is not None:
return last(queue.behind)
else:
return queue
def push(queue, ele):
if isinstance(queue, MyQueue):
last_queue = last(queue)
new_queue = MyQueue(ele)
last_queue.behind = new_queue
def pop(queue):
if queue.behind is not None:
get_queue = queue.behind
queue.behind = queue.behind.behind
return get_queue
else:
print('队列里已经没有元素了')
def print_queue(queue):
print(queue)
if queue.behind is not None:
print_queue(queue.behind)
登入後複製
鍊錶
什麼是鍊錶
鍊錶（Linked list）是一種常見的基礎資料結構，是一種線性
鍊錶（Linked list）是一種常見的基礎資料結構，是一種線性順序數據，而是在每一個節點裡存到下一個節點的指標(Pointer)。由於不必須按順序存儲，鍊錶在插入的時候可以達到O(1)的複雜度，比另一種線性表順序表快得多，但是查找一個節點或訪問特定編號的節點則需要O(n)的時間，而順序表對應的時間複雜度分別是O(logn)和O(1)。
特點
使用鍊錶結構可以克服數組鍊錶需要預先知道資料大小的缺點，鍊錶結構可以充分利用電腦記憶體空間，實現靈活的記憶體動態管理。但是鍊錶失去了數組隨機讀取的優點，同時鍊錶由於增加了結點的指標域，空間開銷比較大。
操作
1、init() :初始化
2、insert() : 插入物
4、delete() : 刪除
5、find( ) : 尋找
實作
此處僅實現雙向清單
class LinkedList():
def __init__(self, value=None):
self.value = value
# 前驱
self.before = None
# 后继
self.behind = None
def __str__(self):
if self.value is not None:
return str(self.value)
else:
return 'None'
def init():
return LinkedList('HEAD')
def delete(linked_list):
if isinstance(linked_list, LinkedList):
if linked_list.behind is not None:
delete(linked_list.behind)
linked_list.behind = None
linked_list.before = None
linked_list.value = None
登入後複製
總結
以上就是利用Python實現基本線性資料結構的全部內容，希望這篇文章對Python幫助。如果有疑問可以留言討論。
更多Python實現基本線性資料結構相關文章請關注PHP中文網！
