考研数据结构之--手撕链表(1)

序言：作为一个科班出身的学生，不会手写链表的话，那可就太嘿嘿嘿了😏😏😏😏😏😏，全部函数名字 取自《王道考研数据结构》

本内容及以后全部代码由c，c++，java这三种语言。代码可以复制粘贴到自己电脑的编译器上调试运行，可能会有bug，那就看你们的眼力见了。哈哈哈哈

首先从最简单的单链表开始讲起：

1.0单链表（c++/c)

线性表的链式存储，普通的数组是每个元素都挨着的，在内存中也是相邻的，而链表只是逻辑上的先后顺序，在内存地址中并不一定是相邻的哦。

顺序存储（数组）的缺点：在我们需要删除或者插入元素的时候，需要移动元素，来补充或者腾出位置来。看下图：

如果数组原来元素就非常多了，元素移位的操作，就会带来极大的时间消耗，这是我们不想看到的！！！

所以，对于需要进行频繁插入，删除元素的操作的时候，我们的单链表应运而生。

链表就引出了指针的内容，重点在于理解理解理解，始终给我记着，指针---地址 ， 指针--指向某个位置的东西

1.1结点定义

前提：结构体的基本语法

单链表的结点是分为两个部分的： 1.数据域（存放元素的位置） 2.指针域（指向下一个结点的位置）

不要告诉我，上面这都看不懂啊。。。

有了这个，我们就可以写出结点的定义代码了

typedef struct LNode{
    int data;  //这里可以是任意类型的, 书上是ElementType
    struct LNode *next;
}Node; //这里书上是LNode

这就定义完了嘞。

每个结点类型我们清楚了，那么整个单链表我们就画得出来了，如下图：

思考一下：单链表能随机存取吗？

1.2 关于带头指针和不带头指针的问题

通过上图可以看出，上面的单链表是没有头指针的，那么，何为头指针呢？头指针就是，我们在单链表中额外申请一个结点，此结点的next指针指向单链表的第一个元素。

看下图带头指针的：

==这样做有什么好处呢？==问题提在这里，后面来分析。记着这个问题啊！！！（可能在后序文章）

接下来的全部这操作都是在 有头指针的 单链表下进行的。

1.3 基本操作的实现

知道了结点定义，一个单链表就是一个一个结点串起来的而已嘛。so easy啦

①创建单链表

问题：给定一个序列（1 3 4 5 9 ），创建链表

有两种方法，第一种是头插法，第二种是尾插法！

先说头插法：顾名思义，每次插入结点都是从头部插入的；看下图过程：

后面的步骤一模一样。我就不画了。

可以发现，创建的链表是逆序的！！

代码部分：（跟着代码，画图，就看的懂了）

//c++
#include <iostream>
using namespace std;
typedef struct LNode {
 int data;
 struct LNode *next;
}Node;
//头插法
//num是创建链表的序列，n是序列的大小
void List_HeadInsert(Node* &head, int num[], int n) {
 head = new Node;
 head->next = NULL;

 for ( int i = 0; i < n; ++i ) {
  Node *s = new Node;
  s->data = num[i];
  s->next = head->next;
  head->next = s;
 }
}
int main()
{
 Node *head;
 int num[] = {1,3,4,5,9};
 List_HeadInsert(head, num, 5);

 Node *p = head->next; // p指针指向head->next,也就是第一个结点
 while ( p ) { //当p不为NULL时
  cout << p->data << ' '; //输出p的数据库
  p = p->next; //p = p->next   =号是从右往左赋值的
 }

 delete head;
 return 0;
}



//c
//为了方便，以后就是c++，毕竟一个new就行了
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode {
 int data;
 struct LNode *next;
}Node;

int main()
{
 Node *head = (Node*)malloc(sizeof(Node));
 head->next = NULL;

 int num[] = {1,3,4,5,9}, i;
 for ( i = 0; i < 5; ++i ) {
  Node *s = (Node*)malloc(sizeof(Node));
  s->data = num[i];
  s->next = head->next;
  head->next = s;
 }

 Node *p = head->next;
 while ( p ) {
  printf("%d ", p->data);
  p = p->next;
 }
 
 return 0;
}

再来看，尾插法：(每次都是从尾部插入元素)

我就直接放代码了，图请读者跟着代码，自己画着看看。

//尾插法
void List_TailInsert(Node* &head, int num[], int n) {
 head = new Node;
 head->next = NULL;
 Node *p = head;
 
 for ( int i = 0; i < n; ++i ) {
  Node *s = new Node;
  s->data = num[i];
  s->next = NULL;
  p->next = s;
  p = s;
 }
}
//创建的序列是顺序的

②查找

==画图，跟着画图==

按序号查找元素

//按序号查找元素(从1开始)
Node* GetElemByIndex(Node* list, int index ) {
 Node *p = list->next;
 int i = 1;
 //index 无效，即<1
 if ( index < 1 ) return list;
 while ( p ) {
  if ( i == index) {
   return p;
  }
  ++i; p =p->next;
 }
 //index大于表长
 return p;
}

按值查找元素

//按值查找
Node* GetElemByValue(Node* list, int v ) {
 Node* p = list->next;
 while ( p && p->data != v) {
  p = p->next;
 }
 return p;
}
//思考：找不到返回值是什么？   NULL

③插入元素

按位置插入

思路就是，找到前一个位置，为什么是前一个位置呢？因为目前我们的单链表是只有next指针，找到结点的前驱结点不方便。

//指定index插入结点
bool Insert( Node* &list, int data, int index ) {
    Node *p = list;
    int i = 1;
    if ( i < 1 ) return false; //index无效
    while ( p && i < index ) {
        p = p->next; i++;
    }
    if ( !p ) return false; //index > 链表长度+1
    Node *s = new Node;
    s->data = data;
    s->next = p->next;
    p->next = s;
    return true;
}

思考：上图中的第一步，和第二步先后顺序能交换吗？

上面是找到指定位置的前一个位置，然后插入。这样是主流的，既方便又方便。然而，假如有一些阴间的要求，我们定义的指针p必须先定位到指定位置index上呢？我们该怎么做呢？

思路：我们仍然是在p指针所指的结点后面插入元素，然后交换这两个结点的data不就行了吗？

我艹。。。。。茅塞顿开

//指定index插入结点
bool Insert2( Node* &list, int data, int index ) {
    Node *p = list;
    int i = 1;
    if ( i < 1 ) return false; //index无效
    while ( p && i <= index ) {
        p = p->next; i++;
    }
    if ( !p ) return false; //index > 链表长度+1
    Node *s = new Node;
    s->data = data;
    s->next = p->next;
    p->next = s;
    //交换值
    int temp = p->data;
    p->data = s->data;
    s->data = temp;
    return true;
}
//在最后一个位置插入需要读者自行修改一下

拓展，插入到指定元素data的前面，请读者自行实现

可以先查找，返回的就是Node*,再插入元素！！

③删除元素

先孤立它，再删除掉！

删除指定位置的元素

请看下图：（删除第二个位置的元素）

//删除指定位置的元素(从位置一开始计数)
bool deleteData(Node* &list, int index) {
 if ( index < 1 ) return false;
 Node *p = list, *q;
 int i = 1;
 while (p && i < index ) {
  p = p->next;
  ++i;
 }
 if ( p == NULL ) return false; //想想为什么
 q = p->next;
 
 p->next = q->next;
 delete q;
 return true;
}

删除指定元素

请读者自行实现，

④求表长度

这还用我来写？？？？

1.4完整代码

//c++
#include <iostream>
using namespace std;
typedef struct LNode {
 int data;
 struct LNode *next;
}Node;
//头插法
//num是创建链表的序列，n是序列的大小
void List_HeadInsert(Node* &head, int num[], int n);
//尾插法
void List_TailInsert(Node* &head, int num[], int n);
//按序号查找元素(从1开始)
Node* GetElemByIndex(Node* list, int index );
//按值查找
Node* GetElemByValue(Node* list, int v );
//指定index插入结点（定位到前一个位置）
bool Insert( Node* &list, int data, int index );
//指定index插入结点（定位到目标位置）
bool Insert2( Node* &list, int data, int index );
//删除指定位置的元素(从位置一开始计数)
bool deleteData(Node* &list, int index);
//输出链表
void outPut(Node *list);

//主函数
int main()
{
 Node *head;
 int num[] = {1,3,4,5,9};
// List_HeadInsert(head, num, 5);
 List_TailInsert(head, num, 5);

 Node *f = GetElemByIndex(head, 1);
 if ( f )
 cout << f->data << endl;

 f = GetElemByValue(head, 10);
 if ( f ) cout << f->data << endl;
 else cout << "No!\n";

 Insert2(head, 99, 1);
 outPut(head);
// Insert2(head, 99, 6);
// outPut(head);

 deleteData(head, 2);
 outPut(head);

 delete head;
 return 0;
}


//头插法
//num是创建链表的序列，n是序列的大小
void List_HeadInsert(Node* &head, int num[], int n) {
 head = new Node;
 head->next = NULL;

 for ( int i = 0; i < n; ++i ) {
  Node *s = new Node;
  s->data = num[i];
  s->next = head->next;
  head->next = s;
 }
}
//尾插法
void List_TailInsert(Node* &head, int num[], int n) {
 head = new Node;
 head->next = NULL;
 Node *p = head;
 
 for ( int i = 0; i < n; ++i ) {
  Node *s = new Node;
  s->data = num[i];
  s->next = NULL;
  p->next = s;
  p = s;
 }
}
//按序号查找元素(从1开始)
Node* GetElemByIndex(Node* list, int index ) {
 Node *p = list->next;
 int i = 1;
 //index 无效，即<1
 if ( index < 1 ) return list;
 while ( p ) {
  if ( i == index) {
   return p;
  }
  ++i; p =p->next;
 }
 //index大于表长
 return p;
}
//按值查找
Node* GetElemByValue(Node* list, int v ) {
 Node* p = list->next;
 while ( p && p->data != v) {
  p = p->next;
 }
 return p;
}
//指定index插入结点（定位到前一个位置）
bool Insert( Node* &list, int data, int index ) {
    Node *p = list;
    int i = 1;
    if ( i < 1 ) return false; //index无效
    while ( p && i < index ) {
        p = p->next; i++;
    }
    if ( !p ) return false; //index > 链表长度+1
    Node *s = new Node;
    s->data = data;
    s->next = p->next;
    p->next = s;
    return true;
}
//指定index插入结点（定位到目标位置）
bool Insert2( Node* &list, int data, int index ) {
    Node *p = list;
    int i = 1;
    if ( i < 1 ) return false; //index无效
    while ( p && i <= index ) {
        p = p->next; i++;
    }
    if ( !p ) return false; //index > 链表长度+1
    Node *s = new Node;
    s->data = data;
    s->next = p->next;
    p->next = s;
    //交换值
    int temp = p->data;
    p->data = s->data;
    s->data = temp;
    return true;
}
//删除指定位置的元素(从位置一开始计数)
bool deleteData(Node* &list, int index) {
 if ( index < 1 ) return false;
 Node *p = list, *q;
 int i = 1;
 while (p && i < index ) {
  p = p->next;
  ++i;
 }
 if ( p == NULL ) return false; //想想为什么
 q = p->next;
 
 p->next = q->next;
 delete q;
 return true;
}
//输出链表
void outPut(Node *list){
 Node* p = list->next;
 while ( p ) {
  cout << p->data << ' ';
  p =p->next;
 }
 cout << endl;
}

1.5 思考题？

1.清空链表怎么写？

2.插入元素，删除元素，的时间复杂度怎么分析？

提示：分为两步分析，第一步找，第二步插入/删除，二者的时间复杂度都要分析出来。