Array(數(shù)組)

image.png

image.png

image.png

1.優(yōu)點(diǎn)：無(wú)論訪問(wèn)哪一個(gè)元素，時(shí)間復(fù)雜度都是 O(1);
2.缺點(diǎn)：刪除，增加元素，時(shí)間復(fù)雜度高，需要遍歷前后移動(dòng)下標(biāo)，所以是 O(n)的時(shí)間復(fù)雜度。刪除時(shí)，調(diào)用垃圾回收機(jī)制size-1。

Linked List(鏈表)

image.png

時(shí)間復(fù)雜度

image.png

1.每個(gè)元素都有兩個(gè)屬性,Value和Next 。它的每一個(gè)元素一般用class定義。Next指向下一個(gè)元素。串在一起形成了一個(gè)鏈表。
2.如果只有一個(gè)指針就叫做單鏈表，
3.可以往前或者往后指，往前指它的先前指針就做（previous）這樣就叫做雙向鏈表。
4.頭指針用Head表示，尾指針用Tail。最后一個(gè)指針?biāo)腘ext指向空，因?yàn)闆](méi)有Next指針了。Tail的Next指針也可以指回到Head來(lái)。這個(gè)就叫做循環(huán)鏈表。

添加刪除操作

image.png

image.png

1.增加或刪除節(jié)點(diǎn)的話，沒(méi)有引起整個(gè)鏈表的群移操作，也不需要復(fù)制元素，挪動(dòng)元素到新的位置，所以它移動(dòng)的效率和修改的操作效率非常高，復(fù)雜度為O(1)
2.這個(gè)結(jié)構(gòu)導(dǎo)致了訪問(wèn)鏈表中的任何一個(gè)位置，操作就不再簡(jiǎn)單了，復(fù)雜度為O(n)

Skip List(跳表)

特點(diǎn)

1.只能用于元素有序的情況。（跳表里的元素始終必須是有序的）不然沒(méi)發(fā)用跳表。
所以，跳表（Skip List）對(duì)標(biāo)的是平衡樹(shù)（AVL Tree）和二分查找，是一種插入/刪除/搜索 都是 O(log n)的數(shù)據(jù)結(jié)構(gòu)。1989年出現(xiàn)。
優(yōu)點(diǎn)：原理簡(jiǎn)單，容易實(shí)現(xiàn)，方便擴(kuò)展，效率更高。因此在一些熱門的項(xiàng)目用來(lái)替代平衡樹(shù)，如Redis，LevelDB 等。

image.png

給有序鏈表加速

1，升緯，添加一級(jí)索引

image.png

2.如果再快加二級(jí)索引

image.png

image.png

image.png

現(xiàn)實(shí)中跳表的形態(tài)

image.png

維護(hù)成本相對(duì)較高，如果增加一個(gè)元素或者刪除一個(gè)元素，都需要把它的索引都更新一遍，在這個(gè)過(guò)程中，它的時(shí)間復(fù)雜度就回編程了logn了

空間復(fù)雜度分析

image.png