Original video:

https://www.youtube.com/playlist?list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P

List

list在insert, remove 的时候所有的元素位置都会移动, 那么这些操作的时间复杂度就会比较高

并且数组满了, 我们都会创建一个新的更大的数组(double size), copy 原来的元素到新的数组

Linked list

先看看list

首地址 : base address

现在定义一个长度为4的 int 数组, 要注意, list 的内存是contiguous的, 现在这种情况就没法extend

那我就重新开辟一个空间, 也就是一个新的array

太小我存不下, 如果我继续存, 那就又存不下了, 怎么办呢? 用linked list

disjoint non-continuous blocks of memory, link them, so store some extra information with each block, so we have two part for each block

linked list : 不是一个连续的list, 而是把每个元素都开辟一个空间, 然后再在后面开辟一个空间, 存下一个元素的地址

一个node由 : int variable 和 pointer variable 组成

时间复杂度 time complexity O(n) big O of n

好处: no extra use of memory

Array vs linked list

cost of accessing an element

so if you want to access elements in the list all the time, array is a better choice

memory requirements

array -fixed size

linked list

这里算linked list占用空间的时候那个 5还没加上去, 现在加上去的话就应该是32 bytes

cost of inserting an element

Implement of linked list in C

这里主要讲的是singly linked list

insert a node at the end of linked list

declare a variable that will store the address of the head node
在数组里存入数据

在c++中, 可以这么写

再添加节点

现在我们创建了一个新的node, 有数据, 有link( 为null), 那么如何把上一个 node 的link 指向这个新的node呢?

我们需要遍历linked list, 然后找到reach the end of the list, 也就是那个link ,红色大括号就是遍历

inserting a node at beginning in linked list

主方法( 这里insert已经定义好了)

定义insert 方法, 添加第一个元素

再添加一个元素

接下来, 定义print方法

累了, 暂时不听了, 要补的后续再来补, 先听关键部分

Doubly Linked List

假如是int, 每个node 占 12个bytes

doubly linked list implement in C

Stack

stack as abstract data type(ADT), 把stack当作抽象数据类型

logic view of stack, also called last-in-first-out(LIFO)

定义:

operations

push(x) : 插入

pop(): remove the most recent item from the stack

top(): return the element at the top of the stack

isEmpty(): 返回boolean

constant time or O(1)

applications

第三个是检查括号的匹配性, 有一个{ 有要有一个 } 来和前面那个括号匹配

infix, postfix, prefix

infix: human readable

postfix, prefix: 才是对machine最友好的, 可以节省infix的括号, 节省内存

infix

因为it's not easy parse and evaluate an infix expression without ambigiouty

所以提出了不需要括号可以无歧义进行分析, 也无需关心操作符的优先级的方法: postfix 和 prefix

prefix
postfix

Queues

把Queues当作抽象数据类型来看(ADT)

first in first out(FIFO)

Queue的地位, 这很重要

Java 中的 LinkedList 类实现了 Queue 接口，因此可以直接用作队列

operations

enqueue(x) , push(x) : 插入

dequeue(), pop() : remove an element form the front head of the queue, 可以让它返回删除的元素

front(), peek() : return the element of the front

isEmpty(): 返回boolean

ifFull()

size(): 获取队列中元素的数量

插入和移除要从不同的sides进行

application

有shared recourses, 先来的先得

Trees

之前将的list, linked list, stack, queue都是linear data structure, 数据是以顺序储存起来的

怎么决定用哪种数据结构?

nodes linked together to simulate hierarchy, non linear structure, 它是一种recursive data structure, 每一个箭头都叫做link

只能从1 ->2 , 不能往回走, 不能从2 -> 1

6和7是Cousins, 不是siblings

在tree中, 如果有n个节点, 那么就有n-1条边

depth and height

depth强调的是到这个node有多少个link(edge), 比如3的深度是1, 7的depth是2, 11的depth是3

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

height强调的是从这个node出发, 到leaf节点, 最长的路线, 所以leaf节点的height为0, 3的height是2

一个是到这个节点, 一个是从这个节点出发