寒假补习1--单链表双链表的基本概念及简单使用

学习动机：在大一时C语言课程设计时老师介绍了许多像链表之类的知识，由于课程设计时间短任务重，感觉十分有用却没有深入学习，一直觉得是心头重担。大二上半学期操作系统实验的算法本来是想用C语言进行实现，但链表知识不充足，最后选择封装方法多的、更为简单的python进行实现。正巧赶上春节假期和肺炎病毒横行，闲着没事做，所以打算每两天补习一项之前因为时间仓促而丢下的知识，希望能坚持下来嘻嘻 ：）

简单链表的概念

百度到的：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。
我的理解：
链表不同于指针，指针必须要线性的进行连接，连续的指向下一个存储单位。链表的组成成分有两个，一个是存储数据的区域，另一个就是指向下一存储区域的指针。

链表与数组的区别

1.数组静态分配内存，链表动态分配内存。
2.数组在内存中是连续的，链表是不连续的。
3.数组利用下标定位，查找的时间复杂度是O(1)，链表通过遍历定位元素，查找的时间复杂度是O(N)。
4.数组插入和删除需要移动其他元素，时间复杂度是O(N)，链表的插入或删除不需要移动其他元素，时间复杂度是O(1)。
————————————————
转自：CSDN博主「哆啦A熊」的原创文章

链表和数组的优缺点

主要体现在插入和删除的效率和内存的占用上。链表的定向插入删除效率会更高一些。内存使用在于数组在声明时便需要声明空间大小且直接开辟空间，而链表只有在连接到时才需要给它分配空间，也无法进行动态分配。
但链表的查找（删除）的效率低，而数组可以进行快速定位，效率较高。

单链表与双链表的实现详解

1.单链表的每一个节点中只有指向下一个结点的指针，不能进行回溯，适用于节点的增加和删除。
2.双链表的每一个节点给中既有指向下一个结点的指针，也有指向上一个结点的指针，可以快速的找到当前节点的前一个节点，适用于需要双向查找节点值的情况。

单链表

单链表的创建：

typedef struct Node  
{  
    ElemType data;              //单链表中的数据域   
    struct Node *next;          //单链表的指针域   
}Node,*LinkedList; 

单链表的初始化：

LinkedList LinkedListInit()  
{  
    Node *L;  
    L = (Node *)malloc(sizeof(Node));   //申请结点空间   
    if(L == NULL)                       //判断是否有足够的内存空间   
        printf("申请内存空间失败/n");  
    L->next = NULL;                  //将next设置为NULL,初始长度为0的单链表   
} 

单链表的建立：

1.头插法：

LinkedList LinkedListCreatH()  
{  
    Node *L;  
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间  
    L->next = NULL;                      //初始化一个空链表  
      
    ElemType x;                         //x为链表数据域中的数据  
    while(scanf("%d",&x) != EOF)  
    {  
        Node *p;  
        p = (Node *)malloc(sizeof(Node));   //申请新的结点   
        p->data = x;                     //结点数据域赋值   
        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL   
        L->next = p;   
    }  
    return L;   
} 

2.尾插法：

LinkedList LinkedListCreatT()  
{  
    Node *L;  
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间  
    L->next = NULL;                  //初始化一个空链表  
    Node *r;  
    r = L;                          //r始终指向终端结点，开始时指向头结点   
    ElemType x;                         //x为链表数据域中的数据  
    while(scanf("%d",&x) != EOF)  
    {  
        Node *p;  
        p = (Node *)malloc(sizeof(Node));   //申请新的结点   
        p->data = x;                     //结点数据域赋值   
        r->next = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL   
        r = p;   
    }  
    r->next = NULL;   
      
    return L;     
} 

3.单链表的插入，在链表的第i个位置插入x的元素

LinkedList LinkedListInsert(LinkedList L,int i,ElemType x)  
{  
    Node *pre;                      //pre为前驱结点   
    pre = L;  
    int tempi = 0;  
    for (tempi = 1; tempi < i; tempi++)  
        pre = pre->next;                 //查找第i个位置的前驱结点   
    Node *p;                                //插入的结点为p  
    p = (Node *)malloc(sizeof(Node));  
    p->data = x;   
    p->next = pre->next;  
    pre->next = p;  
      
    return L;                             

4.单链表的删除，在链表中删除值为x的元素

LinkedList LinkedListDelete(LinkedList L,ElemType x)  
{  
    Node *p,*pre;                   //pre为前驱结点，p为查找的结点。   
    p = L->next;  
    while(p->data != x)              //查找值为x的元素   
    {     
        pre = p;   
        p = p->next;  
    }  
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。   
    free(p);  
    return L;  
}  

main函数

int main()  
{  
    LinkedList list,start;  
/*  printf("请输入单链表的数据：");  
    list = LinkedListCreatH(); 
    for(start = list->next; start != NULL; start = start->next) 
        printf("%d ",start->data); 
    printf("\n"); 
*/  printf("请输入单链表的数据：");   
    list = LinkedListCreatT();  
    for(start = list->next; start != NULL; start = start->next)  
        printf("%d ",start->data);  
    printf("\n");  
    int i;  
    ElemType x;  
    printf("请输入插入数据的位置：");  
    scanf("%d",&i);  
    printf("请输入插入数据的值：");  
    scanf("%d",&x);  
    LinkedListInsert(list,i,x);  
    for(start = list->next; start != NULL; start = start->next)  
        printf("%d ",start->data);  
    printf("\n");  
    printf("请输入要删除的元素的值：");  
    scanf("%d",&x);  
    LinkedListDelete(list,x);   
    for(start = list->next; start != NULL; start = start->next)  
        printf("%d ",start->data);  
    printf("\n");  
      
    return 0;  
}

双链表

双链表的创建

typedef struct DulNode
{
	int data;
	struct DulNode *next,*prior;
}DulNode,*DulLinkList;

双链表的初始化

Status InitList_DUL(DulLinkList &L)//初始化一个带头结点的双向循环链表  
{
	L=(DulNode*)malloc(sizeof(DulNode)); 
	L->next=L;
	L->prior=L;
	if (!L) 
		exit(OVERFLOW);
	return OK;
}

正序创建一个带头结点的双向循环链表

void CreateList_DUL(DulLinkList &L)表,ok
{	
	DulLinkList p,s;//中间变量
	int n,i;
	printf("input Length: \n");
	scanf("%d",&n);
	p=L;
	printf("input value with enter:");
    for(i=n;i>0;i--)
	{		
		s=(DulLinkList)malloc(sizeof(DulNode));
		scanf("%d",&s->data);
		p->next=s;
		s->prior=p;
		p=s;
	}
	p->next=L;
	L->prior=p;
}

定位值为e的结点的位置

DulLinkList LocateELem_DUL(DulLinkList L,ElemType x)   
{//定位值为e的结点的位置
  DulNode *p;
  p=L->next;
  while(p!=L)
  {
	  	if(!compare(x,p->data))
			return p;
		p=p->next;
  }
  printf("the element is not exists\n");
  return NULL;
}

在带头结点的双向循环链表中的x值后插入y值

Status InsertAfter_DUL(DulLinkList &L,ElemType y)
	DulLinkList p,s;
	ElemType x;
	printf("value you want to find is :");
	scanf("%d",&x);
    p=LocateELem_DUL(L,x);
	if(!p)
	{
		printf("%d not exists.\n",x);
		return ERROR;
	}
	s=(DulLinkList)malloc(sizeof(DulNode));
	s->data=y;
	s->next=p->next;
	p->next->prior=s;
	p->next=s;
	s->prior=p;
	return OK;
}

删除

DulNode* deleteTheNode(DulNode* head,int num)  
{  
    DulNode* p1,*p2;  
    p1=head;  
    while (p1->next&&num!=p1->data)  
    {  
        p1=p1->next;  
    }  
    if (num==p1->data)  
    {  
        if (p1==head)//找到的是头节点  
        {  
            head=head->next;  
            head->prior=NULL;  
        }  
        else if(p1->next)//不是头结点,也不是尾节点  
        {  
            p1->next->prior=p1->prior;  
            p1->prior->next=p1->next;  
        }  
        else  
        {  
            p1->prior->next=NULL;  
          
            free(p1);  
        }  
    }  
    else  
    {  
        //cout<<"节点未找到"<<endl;  
		printf("节点未找到");
    }  
    return head;  
}  

main函数

void main()
{
	DulLinkList p;
	DulLinkList L;
	InitList_DUL(L);
//	NCreateList_L(L);//逆位序建立链表
    CreateList_DUL(L);//正序建立双向循环链表
	ListTraverse_DUL(L);
//	ListPrint_L(L);
//	Reverse_DulLinkList(L);//OK
//	ListTraverse_DUL(L);
//	ListPrint_DUL(L);
	ElemType y;
	printf("the insert value is :");
	scanf("%d",&y);
//	InsertBefore_DUL(L,y);//OK
	InsertAfter_DUL(L,y);  //OK
	ListTraverse_DUL(L);
//	ListPrint_DUL(L);

	ElemType z;
	printf("the delete value is :");
	scanf("%d",&z);
	deleteTheNode(L,z);
	ListTraverse_DUL(L);
}

写在最后

随着这篇博客的完成，我也大致了解了链表的概念和基本的实现方法。代码部分大多借鉴优秀的csdn博客博主：@Mr.Gzj ，表示感谢。
因为还没有学习数据结构，发现很多知识都是和数据结构相关的，所以还是有许多存疑的地方，希望这个假期有时间提前学习一下数据结构然后解决掉它~加油加油！