• node (noun)

a place on a tree from which a branch grows

image.png

data structure

• linked list

a linked list consists of a group of nodes which together represent a sequence. Each node contains two things:the actual data being stored and a pointer to the next node in the sequence. There are also doubly linked lists where each node has a pointer to both the next item and the previous item in the list.The most basic operations in a linked list are adding an item to the list,deleting an item from the list,and searching the list for an item.

image.png

Linked list time complexity

╔═══════════╦═════════╦════════════╗
║ Algorithm ║ Average ║ Worst Case ║
╠═══════════╬═════════╬════════════╣
║ Space     ║ O(n)    ║ O(n)       ║
║ Search    ║ O(n)    ║ O(n)       ║
║ Insert    ║ O(1)    ║ O(1)       ║
║ Delete    ║ O(1)    ║ O(1)       ║
╚═══════════╩═════════╩════════════╝

总结：

查找:数量越多，时间越久
插入：马上定位 ，马上插入
删除：马上定位，马上删除

• 在不用临时变量的情况下如何交换两个变量的值

假设有a，b两个变量，把a 和 b 相加，和减去b就是a的值，和减去a的值就是b的值
代码

void swap(int a,int b){
    a = a + b;
    b = a - b;// 和减去b是a，b等于了a
    a = a - b;//和减去a的值等于b，a成了b的值
    printf("a ====  %d,b ==== %d",a,b);
}

进阶版

• 使用XOR算法，不会有溢出的风险，效率更高
• XOR means one or the other,but not both

void swap(int a,int b){
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    printf("a ====  %d,b ==== %d \n\n\n\n\n\n\n\n\n\n\n\n\n",a,b);
}

• Stack

A stack is a basic data structure where you can only insert or delete items at the top of the stack.It's kind if similar to a stack of books.If you want to look at a book in the middle of the stack you must take all of the books above it off first.The stack is considered LIFO(Last In First Out) -- meaning the last item you put in the stack is the first item that comes out of the stack.

image.png