Array (陣列)
首先，我們先從簡單常見的資料結構介紹(前面幾篇都是簡單常見的資料結構介紹，覺得無聊的其實完全可以跳過~~)，Python 內建的資料結構並無陣列array(內建的有:list, tuple, set, dictionary)。在某些資料結構的使用上，Array會比List來的有效率。在這裡我們使用numpy的array來demo。這裡我們先介紹一下array的幾個特性:
- Array不像是List，在array中資料其資料型態(data type)要一致。
- Array和List一樣，每個元素在記憶體裡是連續存放的。(之後跟linked list比較應該會比較印象深刻)
- Array的每個元素有自己的索引(unique index)方便索引。

我們這裡先介紹一維陣列的幾個功能，所有code大家可以自己在jupyter notebook裡跑跑看，多維陣列的操作，在學深度學習的資料處理時蠻常遇到的，感覺算是實用的小工具:

創建一個一維陣列，時間複雜度: O(N)，空間複雜度: O(N)。

import numpy as np
myarray=np.array([1,5,2,70,9,6])

在陣列中插入資料，時間複雜度: O(N)，空間複雜度:O(1)。因為在最差的情況下，是在第一個位子插入資料，後面所有index都要+1，故時間複雜度O(N)。

myarray=np.insert(myarray,0,30)
myarray

走訪陣列(array traversal): 拜訪array中每個資料，時間複雜度: O(N)，空間複雜度: O(1)

def traversal(myarray):
    for i in myarray:
        print(i)
traversal(myarray)

用索引(index)取得陣列中的資料，時間複雜度O(1)，空間複雜度O(1)。

myarray[3]

搜尋陣列中的資料，時間複雜度O(N)，空間複雜度O(1)

def search(array,element):
    for i in range(len(array)):
        if array[i]==element:
            return f'the index of {element} is {i}'
        else:
            return f'{element} is not in the array'
search(myarray,8)

刪除陣列中的資料，時間複雜度: O(N)，空間複雜度:O(1)。原因一樣，最壞的情況是刪除第一筆資料，陣列中所有資料的index都改變。

np.delete(myarray,0,axis=0)

二維陣列
創建m x n的二維陣列，時間複雜度O(mn)，空間複雜度O(mn)

my2Darray=np.array([[13,5,7,9],[45,3,12,1],[79,6,51,3],[55,6,33,2],[10,19,22,78]])
my2Darray
#可以透過my2Darray.shape來檢查陣列的形狀,這個例子裡 output:(5,4) 

在二維陣列中插入資料，時間複雜度O(mn)，空間複雜度O(1)。

# insert list in first dimension, my2Darray.shape output: (6,4)
#檢查shape和insert完後的array
my2Darray=np.insert(my2Darray,0,[1,2,3,4],axis=0)
my2Darray.shape, my2Darray

# insert list in second dimention, my2Darray.shape output: (6,5)
#檢查shape和insert完後的array
my2Darray=np.insert(my2Darray,0,[1,2,3,4,5],axis=1)

#檢查shape和insert完後的array
my2Darray.shape, my2Darray

用index取得二維陣列中的資料，時間複雜度O(1)，空間複雜度O(1)。

my2Darray[0][2]

走訪二維陣列(2D array traversal)，時間複雜度O(mn)，空間複雜度O(1)。

for i in range(my2Darray.shape[0]):
    for j in range(my2Darray.shape[1]):
        print(my2Darray[i][j])

搜尋二維陣列中的資料，時間複雜度O(nm)，空間複雜度(1)。

def find_element(target):
    for i in range(my2Darray.shape[0]):
        for j in range(my2Darray.shape[1]):
            if my2Darray[i][j]==target:
                return f'the index of {target} is ({i},{j})'
    return f'the element is not in the array'
find_element(10)

##其實numpy裡還有一個內建搜尋功能如下，直接回傳想找的element的index
np.where(my2Darray==10)

刪除二維陣列中的資料，時間複雜度: O(nm)，空間複雜度: O(nm)

#delete row
np.delete(my2Darray,0,axis=0)
#delete column
np.delete(my2Darray,0,axis=1)

Python Lists (列表)
列表為一資料結構用來儲存一系列有序的資料，不同於array，列表內的資料不需要型態(type)一樣，舉例來說，一個列表內可以有列表、整數、字串.......。
從下面這個例子可以看到，array把所有數字自動轉成字串，而list還是保佑原來數字的資料型態。

## For python list
Mylist=['Mary',2,'George',20]
Myarray=np.array(['Mary',2,'George',20])
#可以看到在Mylist裡面，2還是int(整數)，但在Myarray裡面，2變成了string(字串)
type(Mylist[0]), type(Myarray[0]), type(Mylist[1]), type(Myarray[1])
#output: (str, numpy.str_, int, numpy.str_)

下面給大家複習一下list的不同操作:
創建一個list，時間複雜度: O(N) ，空間複雜度: O(N)。

mylist=[1,2,3,4]

走訪列表(list traversal):時間複雜度O(N),空間複雜度: O(1)

for i in mylist:
    print(i)
# 或是也可以寫成
for i in range(len(mylist)):
    print(mylist[i])

插入資料於列表中(list)，時間複雜度O(N)，空間複雜度: O(1)。

mylist.insert(0,5)
#output: [5, 1, 2, 3, 4]
mylist

插入資料於列表最後(append)，時間複雜度O(1)，空間複雜度O(1)。

mylist.append(60)
#output:[5, 1, 2, 3, 4, 60]

插入一個列表於另一個列表後，時間複雜度O(n)，空間複雜度O(n)。

new_element_list=[10,20,30]
mylist.extend(new_element_list)
mylist
#output:[5, 1, 2, 3, 4, 60, 10, 20, 30]

列表其他內建的刪除方法

#回傳最後一個值，時間複雜度O(1)，空間複雜度:O(1)
mylist.pop()
mylist
#output:30
#output:[5, 1, 2, 3, 4, 60, 10, 20]

#pop也可以指定刪除的元素位子，時間複雜度O(N)，空間複雜度:O(1)
mylist.pop(1)
mylist
#output:1
#output:[5, 2, 3, 4, 60, 10, 20]

#也可以使用del，時間複雜度O(N)，空間複雜度:O(1)
#刪除第一個元素
del mylist[0]
#刪除前三個元素
del mylist[0:3]

#也可以使用remove直接刪除列表中的值，時間複雜度O(N)，空間複雜度:O(1)
#假使mylist=[5, 2, 3, 4, 60, 10, 20]
mylist.remove(60)
mylist
#output:[5, 2, 3, 4, 10, 20]

在列表中搜尋，時間複雜度:O(N)，空間複雜度:O(1)

def search(mylist,target):
    for i in mylist:
        if i==target:
            return f'{target} is in the list' 
    return f'{target} is not in the list'
search(mylist,20)
#output:'20 is in the list'

看到這裡，大家可能覺得列表跟一維陣列幾乎一樣，其實還是有一些不一樣，除了前面提到資料型態(data type)不同外，當我們用一些符號操作的結果也完全不同

# list concatenate:
a_list=[1,2,3,4]
b_list=[5,6,7,8]
a_list+b_list
#output=[1, 2, 3, 4, 5, 6, 7, 8]

#array的加法
a_array=np.array([1,2,3,4])
b_array=np.array([5,6,7,8])
a_array+b_array
#output=array([ 6,  8, 10, 12])

# list append了四個一樣的list
a_list*4
#output=[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]

# array 所有的element*4
a_array*4
#output=array([ 4,  8, 12, 16])

參考資料:
本文主要為udemy課程: The Complete Data Structures and Algorithms Course in Python的學習筆記，有興趣的人可以自己上去看看。