數(shù)組
數(shù)組的存儲(chǔ)空間在內(nèi)存空間中是連續(xù)的,執(zhí)行插入莲祸、刪除操作需要移動(dòng)后續(xù)元素,對(duì)應(yīng)操作的時(shí)間復(fù)雜度:
-
prependO(1) -
appendO(1) -
lookupO(1) -
insertO(n) -
deleteO(n)
鏈表
鏈表中節(jié)點(diǎn)之間通過(guò)next或者pre指針關(guān)聯(lián),執(zhí)行插入亚隅、刪除操作比較方便,但是鏈表的查找不會(huì)想數(shù)組那么輕松
-
prependO(1) -
appendO(1) -
lookupO(n) -
insertO(1) -
deleteO(1)
跳表
- 建立在鏈表基礎(chǔ)之上,并且鏈表元素必須要是有序的,跳表對(duì)應(yīng)的是平衡樹(shù)富俄、二分查找
- 在有序的鏈表上,為了提高鏈表的查找效率,可以通過(guò)升維的方式,添加一級(jí)索引,二級(jí)索引..的方式提高查詢效率
- 時(shí)間復(fù)雜度O(log n)
- 空間復(fù)雜度O(n)
樹(shù)
鏈表的一個(gè)節(jié)點(diǎn)只有一個(gè)next指針,如果有兩個(gè)next或者多個(gè)指針,那么就形成樹(shù),有兩個(gè)next指針的稱為二叉樹(shù)
圖
如果樹(shù)狀結(jié)構(gòu)中存在環(huán),那么就稱為圖,樹(shù)是一種特殊的圖
二叉搜索樹(shù)
- 又稱二叉搜索排序樹(shù),有序二叉樹(shù),
- 是一個(gè)
空樹(shù),或者中序遍歷結(jié)果為升序 - 時(shí)間復(fù)雜度O(log n)
- 刪除操作如果是刪除的子樹(shù)的根節(jié)點(diǎn),那么一般把大于該節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)拿上來(lái)填充
- 中序遍歷為升序
