单向链表
链表相比于顺序表,优点事他能比较方便地插入和删除元素。但是链表不能随机存取。
定义一个单向链表
链表里的node相比于顺序表的的区别是,链表的会多一个domain来放指向下一个node的pointer。
struct linkedNode {
int value;
linkedNode* next;
}
typedef struct linkedNode linkedNode;
typedef struct linkedNode* linkedList;
偷懒点可以写成
typedef struct linkedNode {
int value;
linkedNode* next;
} linkedNode, * linkedList;
其中,
第5行的意思是,把这个结构体直接rename成linkedNode
,这样就不用在后续代码里写一大坨有的没的。
第6行的linkedList
是一个指向struct linkedNode
的pointer。
因为一个链表是由各个node是通过next
这个pointer来link在一起的,换句话说,只要有第一个node的pointer就能找到一整个表。
所以在表示一个单链表的时候,只要declare一个pointer指向这个单链表的第一个node就可以了。
综上所述,要declare一个新的单链表,只需要
linkedList list;
// 或
linkedNode* list;
/* 两种写法二选一即可,在电脑看来,两个写法都是一样的。
* 只不过在人的角度来看,前者强调的是一整个表,
* 后者强调的是单单一个node。
* 合适的地方用合适的名字,代码可读性up
*/
就可以了。
一些操作.h
因为书上经常malloc()
导致我看得头昏眼花,所以我把他封装成一个function.
linkedNode* newNode() {
return (linkedNode*) malloc(sizeof(linkedNode));
// ~~~~~~~~~~~~~ 记得typecasting,不然翻车
}
还有这个,在某个node后面插入一个新node
bool insertAfter(linkedNode* p, int value) {
if (p == NULL) { // 如果i的位置比整个表还要大
return false;
}
else {
linkedNode* newNode = newNode();
newNode->value = value;
newNode->next = p->next;
p->next = newNode;
return true;
}
}
不带头节点的单链表
初始化
初始化的方法,这时候表里面还没有东西
bool initList(linkedList &list) {
// ~~~~~ 注1
list = NULL;
return true;
}
要特意让这个list的地址里的数据变成NULL
的原因是为了防止这块地址有用剩下的脏数据——换句话说就是为了防止上一个人拉完屎不冲厕所,我们不管怎么样,开始方便之前都先给他冲一下。
注1:注意传参的时候一定要是引用那个表,就是前面加个&
。如果没有&
的话,接下来的都是对这个list的复制品进行操作。
然后再需要创建一个新表的地方,比如说在main()
里,就
linkedList list;
// 注意,linkedList实际上是一个pointer
initList(list);
判断这个单向链表是不是空的
只要看看这个头指针是不是null
bool isEmpty(linkedList list) {
if (list == NULL) {
return true;
}
else {
return false;
}
}
在第i个之后插入
没有头节点,要先判断它要插入的位置是不是第一个,然后分不同情况来处理。
这个写起来比较阴间。
bool insert(linkedList &list, int i, int value) {
if (i < 1) {
return false;
}
if (i == 1) {
linkedNode* newNode = newNode();
newNode->value = value;
newNode->next = list;
list = newNode;
// 把你鲨叻,我替你活下去
return true;
}
else {
linkedNode* p = list;
int count = 1;
while (p!=NULL && count < i-1) {
p = p->next;
count = count +1;
}
return insertAfter(p, value);
}
}
带头节点的单链表
初始化
头节点自身不存储数据,他只是为了让一些操作变得方便一点点。
有头节点的不能让电脑自动分配,要手动malloc()
bool initList(linkedList &list) {
list = newNode();
list->next = NULL;
// 空表,头节点没有后继节点
return true;
}
然后它创建新表和上面一样。
linkedList list;
initList(list);
判断是不是空的表
上面说过它的特性,只要判断头节点的后继节点指针是不是null
bool isEmpty(linkedList list) {
if (list->next == NULL) {
return true;
}
else {
return false;
}
}
在第i个之后插入
比如说我现在想在第i
个位置插入一个node。
bool insert(linkedList &list, int i, int value) {
if (i < 1) {
return false; // 插入位置不对,直接让它爬
}
linkedNode* current; // 表示当前扫描到的node
int count = 0; // 表示p现在是第几个node
current = L; // 让p指向头节点
while (current != NULL && count < i-1) { //一直扫到第i-1个node
current = current->next;
count = count +1;
}
return insertAfter(current, value);
}
最坏的时间复杂度是 O(n)
。
删除第i个
扫描、unlink、free()
.
这种要传表头指针进来的。
bool delete(linkedList &list, int i) {
if (i < 1) { //不解释了
return false;
}
linkedNode* current = list;
int count = 0;
while (current != NULL && count < i-1) { //扫描
current = current->next;
count = count +1;
}
if (current == NULL OR current->next == NULL) {
return false;
}
linkedList* toBeDelete = current->next;
current->next = toBeDelete->next; // unlink
free(toBeDelete); // free()
return true;
}
}
最差时间复杂度 O(n)
删除指定一个node,不给表头指针
穿上他的衣服,让他替你去死,你变成他活下去。
bool delete(linkedList* node) {
// 你不能杀死一个死人
if (node == NULL) {
return false;
}
node->value = node->next->value;
node->next = node->next->next;
return true;
}
…算了就这样吧,这块内存这样一搞是个事故物件那我就不要了 :-)
在指定某个node之前插入数据
如果它给了表头给你,就可以从0开始重新扫一遍来搞。如果没有给,就要狸猫换太子。
bool insertBefore(linkedNode* current, int value) {
if (current == NULL) {
return false;
}
else {
linkedNode* newNode = newNode();
newNode->next = current->next;
current->next = newNode;
newNode->value = current->value;
current->value = value;
}
}
按位序查找
其实上面已经有一些实现了按照位序查找了
以下方法实现了输入一个链表表头就返回第i个node
linkedNode* getElement(linkedList list, int i) {
if (i < 0) {
return NULL;
}
else {
linkedNode* current = list;
int count = 0;
while (current != NULL AND count < i) {
current = current->next;
count = count +1;
}
return current;
}
}
按值查找
linkedNode* locateElement(linkedList list, int value) {
linkedNode* current = list->next;
while(current != NULL AND current->value != value) {
current = current->next;
}
return current;
}
求表的长度
int length(linkedList list) {
int length = 0;
linkedNode* current = list;
while(current->next != NULL) {
current = current->next;
length = length +1;
}
return length;
}
2021年5月27号更新:
感谢猪肝大佬指出了两处英文单词拼写错误,现在已经更正
下次一定会注意 >///<
知识共享署名-署名-非商业性使用-相同方式共享 4.0 国际许可协议