数据结构*单链表

单链表定义

定义

单链表（Singly Linked List）是一种链式存储的数据结构，由一系列节点（Node）组成，每个节点包含两个部分：

1. 数据域（Data）：存储数据。
2. 指针域（Next）：存储指向下一个节点的地址。

例如：

typedef struct node(){
	int id; //数字域
	node* p; //指针域
}Node;

时间复杂度

• 数组
  • 查找效率更高，但插入和删除（非尾部）操作较慢。
• 单链表 插入和删除效率较高（尤其是头部），但查找效率较低。

操作	单链表（Singly Linked List）	数组（Array）
查找	O(n)（需要从头遍历）	O(1)（可通过索引直接访问）
插入	O(1)（直接修改指针）	O(n)（需要移动元素）
删除	O(1)（直接修改指针）	O(n)（需要移动元素）

基本操作

初始化

Node* initlist()
{
	Node* head = (Node*)malloc(sizeof(Node));
	head->data=0;
	head->next=NULL;
	return head;

}

遍历

void listnode(Node *L){
	Node *p=L->next;
	while(p!=NULL){
	printf("%d ",p->data);
	p=p->next;
	}
	printf("\n")
}

推广：获取链表长度

int listnode(Node *L){
    Node *p=L->next;
    int i=0;
    while(p!=NULL){
    i++
    p=p->next;
    }
    printf("%d",i);
    return 0;
}

增

在单链表中，插入又分为：

• 头插法
• 尾插法
• 寻找特定位置插入

头插法

void inserthead(Node* L;int id){
	Node* p=(Node*)malloc(sizeof(Node));
	p->data=id;
	p->next=L->next;
	L->next=p;
}

尾插法

void append(Node *L){
    Node *temp=L;
    while (temp->next) { // 遍历到链表尾部
        temp = temp->next;
    }
    temp->next = p;
}

指定位置插入

int inseretnode(Node *L,int pos, int e){
    Node *p=L;
    for(int i=0;i<<pos-1;i++){
		p=p->next;
    	if(p==NULL)
            return 0;
    }
    
    Node* q=(Node*)malloc(sizeof(Node));
    q->data=e;
    q->next=p->next;
    p->next=q;
    return 1;
}

删

删除单个节点

int deletenode(Node *L,int pos){
	Node *p=L;
	for(int i=0;i<pos-1;i++){
		p=p->next;
		if(p==NULL)
			return 0;
	}
	if(p->next==NULL)
	{
		printf("error");
		return 0;
	}
	Node* temp = p->next;
	p->next=p->next->next;
	free(temp);
	return 0;
}

删除整个链表

void freelist(Node *L){
    Node* current = L;
    Node* nextNode;
    while (current!=NULL) {
        nextNode = current->next; 
        free(current);            
        current = nextNode;       
    }
}

查

查看全部节点(遍历)

void listnode(Node *L){
    Node *p=L->next;
    while(p!=NULL){
    printf("%d ",p->data);
    p=p->next;
    }
    printf("\n")
}

查看特定的节点

应用

快慢指针查找倒数第k个节点

删除绝对值相等的节点

三指针反转链表