单链表 订阅
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。 展开全文
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
信息
外文名
Singly Linked List
类    型
数据结构元素
建立过程
申请空间、得到数据、建立链接
中文名
单链表
简    介
地址任意的存储单元存放数据元素
实    质
一种链式存取的数据结构
单链表单链表简介
链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表(单链表),单链表是链式存取的结构。链接方式存储的线性表简称为链表(Linked List)。链表的具体存储表示为:① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的)② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link))链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。┌───┬───┐│data │next │└───┴───┘data域--存放结点值的数据域next域--存放结点的直接后继的地址(位置)的指针域(链域)链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的,每个结点只有一个链域的链表称为单链表(Single Linked List)。单链表中每个结点的存储地址是存放在其前趋结点next域中,而开始结点无前趋,故应设头指针head指向开始结点。链表由头指针唯一确定,单链表可以用头指针的名字来命名。终端结点无后继,故终端结点的指针域为空,即NULL。
收起全文
精华内容
下载资源
问答
  • 单链表

    千次阅读 多人点赞 2019-08-05 15:50:59
    带头结点和不带头结点的单链表 带头结点的单链表,头指针head指向头结点,头结点的值域不包含任何信息,从头结点之后的结点开始存储信息。 头指针head不等于NULL,head->next等于NULL时,链表为空。 ...

     

     一、基本概念

    带头结点和不带头结点的单链表

    带头结点的单链表,头指针head指向头结点,头结点的值域不包含任何信息,从头结点之后的结点开始存储信息。

    头指针head不等于NULL,head->next等于NULL时,链表为空。

     

    单链表结点定义

    typedef struct LNode{

        int data;   //data存放结点数据域

       struct LNode *next;    //指向后继结点的指针

    }LNode;  //定义单链表结点类型

    引入头结点的好处:(1)无论链表是否为空,头指针总指向头结点的非空指针,(2)开始结点的位置存放在头结点的指针域中,所以链表的第一个位置上的操作和其他位置一致,方便

    1. 建立单链表

    (1)头插法

    从一个空表开始,生成新结点,将读到的数据存放到新结点的数据域,然后将新结点插入到当前两边的表头,即头结点之后

    (头插法生成的链表中结点的次序和输入数据的顺序不一致)

    关键代码:

    LNode *s;int x;
    L=(LinkList)malloc(sizeof(LNode)); //创建头结点
    L->next=NULL;                  //初始链表为空
    /*....*/
    s=(LNode)malloc(sizeof(LNode));  //创建新结点
    s->data=x;
    s->next=L->next;
    L->next=s;                        //将新结点插入表中,L尾头指针
    

    (2)尾插法

    将新结点插入到当前链表的表尾,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。

    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;  //r为表尾指针
    /***/
    while(x!=maxSize){
    s=(LNode *)malloc(sizeof(LNode));
    s->data=x;
    r->next=s;
    r=s;                  //r指向新的表尾结点
    }
    r->next=NULL;      //尾节点置空
    return L;

     2.按序号查找结点值(O(n))

    在单链表中从第一个结点出发,顺指针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点指针域NULL;

    LNode *GetElem(LinkList L,int i){
        int j=1;          //计数,初始为1
        LNode *p=L->next;   //头结点指针赋给p
        if(i==0)
            return L;    //若i等于0,返回头结点
        if(i<1)
            return NULL; //若i无效,返回NULL
        while(p&&j<i){  //从第1个结点查找第i个结点
            p=p->next;
            j++;
    }
    return p;
    }

    3.按值查找(O(n))

    从单链表第一个结点开始,由前往后依次比较表中个结点数据域的值,若某个结点数据域的值等于给定值e,则返回该结点指针;若整个单链表无值相等的结点,则返回NULL;

    LNode *Locate(LinkList L,ElemType e){
            LNode *p=L->next;
            while(p!=NULL &&p->data!=e) //从第1个结点开始查找data域为e的结点
                p=p->next;    
    
            return p;    //找到后返回该结点指针,否则返回NULL
    }

    4.插入(O(n))

    要把x插入到第i个位置,先检查位置是否合法,然后找到待插入位置的前驱结点,即第i-1个结点,再往其后插入新结点

    步骤(1)调用序号查找算法GetElem  查找第i-1个结点。假设返回的第i-1个结点为*p

              (2)令新结点*s的指针域指向*p的后继结点,

               (3)再令结点*P的指针域指向新插入的结点*s

    p=GetElem(L,i-1);//查找插入为止的前驱结点
    s->next=p->next;   //图中1
    p->next=s;         //图中2

     

    5.删除(O(n))

    要删除第i个结点。先检查删除位置的合法性,然后查找表中第i-1个位置,即被删除结点的前驱结点,再将其删除

    假设结点*p为找到的被删除结点的前驱结点,为实现这一操作的逻辑关系的变化,仅需修改*p的指针域,即将*p的指针域next指向*q的下一结点

     

    p=GetElem(L,i-1);      //查找删除位置的前驱结点
    q=p->next;              //令q指向被删除结点
    p->next=q->next;            //将*q结点从链中断开
    free(q);                  //释放结点的存储空间

     拓展删除指定结点:

    先从表头结点开始顺序找到其前驱结点,然后执行删除

    p=p->netx;   //令q指向*p的后继结点

    p->data=p->next->data;    //和后继结点交换数据域

    p->next=q->next;       //将*q结点从链中断开

    free(q)

    6.求表长操作

    实质为计算数据结点(不含头结点)的个数,需要从第一个开始遍历全部结点。

    *p=first->link;
    int count=0;
    while(p!=NULL){
        p->link;count++;
    }
    return count;

     

    #include <stdio.h>
    #include <stdlib.h>
    //头插法
    #define SIZE 5
    
    #define ERROR 1
    #define OK     0
    
    /* 数据元素类型 */
    typedef int ListType;
    
    /* 单链表结点定义 */
    typedef struct LNode
    {
     ListType data;      // 数据域
     struct LNode *next; // 指针域,指向直接后继元素
    }LNode;
    
    /* 函数的声明 */
    LNode *HeadCreateList(void);// 使用头插法创建一个单链表
    LNode *TailCreateList(void);// 使用尾插法创建一个单链表
    void PrintfList(LNode *L);  // 打印输出链表
    
    
    
    int main(void)
    {
     LNode *L1 = NULL;
     LNode *L2 = NULL; 
     
     /* 使用头插法创建单链表 */
     L1 = HeadCreateList();
     printf("头插法创建的链表为:");
     PrintfList(L1);
     return 0;
    }
    
    
    LNode *HeadCreateList(void)//头插法 
    {
     int i;
     LNode *L;  // 头结点
     LNode *s;  // 新结点
     L->next = NULL;  // 此时链表为空
     // 创建链表
     for (i = 0; i < 5; i++)
     {
       // 创建新结点
       s = (LNode*)malloc(sizeof(LNode));
       s->data = i;
       // 使用头插法把新元素插入到链表中
       s->next = L->next;  // 新结点的next指针指向头结点
       L->next = s;    // 头结点的next指针指向新结点
     }
     
     return L;
    }
    
    
    
    void PrintfList(LNode *L)
    {
     LNode *temp = L;
     
     while(temp->next)
     {
       temp = temp->next;
       printf("%d ",temp->data);
     }
     printf("\n\n");
    }

     

    展开全文
  • 单链表-源码

    2021-02-08 03:07:32
    单链表
  • 创建单链表的头插法与尾插法详解

    万次阅读 多人点赞 2018-09-26 20:54:30
    创建单链表 关于数据结构的入门,就是从顺序表和单链表开始。 我们不讲顺序表,直接从单链表开始我们的数据结构和算法的学习之路。 单链表就是一种特殊的结构体组合而成的数据结构,关于单链表的创建方法有很多种,...

    创建单链表

    关于数据结构的入门,就是从顺序表和单链表开始。
    我们不讲顺序表,直接从单链表开始我们的数据结构和算法的学习之路。

    单链表就是一种特殊的结构体组合而成的数据结构,关于单链表的创建方法有很多种,但都大同小异。

    在这里插入图片描述

    正如这幅图中所表示的那样,单链表就是由可能不连续的数据所组合而成的数据结构。 其中每个数据分为两部分,一部分是数据存储的位置,称为数据域,另外指针所存储的地方,称为指针域

    typedef struct Node {
    	int data;                    // 存储链表数据
    	struct Node *next;     		//  存储结点的地址
    }LNode,*Linklist;
    

    在进入创建链表之前,我们先写好主函数的用来输出的输出函数。

    void Illustrate(Linklist head) {
    	Linklist tem = head;                 //  将头指针的地址赋给临时的指针
    	while (tem->next != NULL) {       //  指向最后一个结点的指针域时会停止
    		tem = tem->next;               //  结点不断向后移动
    		printf("%d\n", tem->data);
    	}
    }
    
    int main() {
    	Linklist head = NULL;            //  链表的头指针
    	head = Creat_list(head);        //  创建链表
    	Illustrate(head);               //  输出每个结点的数据域
    	system("pause");
    	return 0;
    }
    

    头插法创建单链表

    在这里插入图片描述

    头插法代码:

    Linklist Creat_list(Linklist head) {
    	head = (Linklist)malloc(sizeof(Lnode));      //  为头指针开辟内存空间
    	Lnode *node = NULL;                    //  定义新结点
    	int count = 0;                          //  创建结点的个数
    	head->next = NULL;              
    	node = head->next;              	//  将最后一个结点的指针域永远保持为NULL
    	printf("Input the node number: ");
    	scanf("%d", &count);
    	for (int i = 0; i < count; i++) {
    		node = (Linklist)malloc(sizeof(Lnode));     //  为新结点开辟内存空间
    		node->data = i;               //  为新结点的数据域赋值
    		node->next = head->next;          //  将头指针所指向的下一个结点的地址,赋给新创建结点的next 
    		head->next = node;          //  将新创建的结点的地址赋给头指针的下一个结点
    	}
    	return head;
    }
    

    头插法创建链表的根本在于深刻理解最后两条语句

    	node->next = head->next;          //  将头指针所指向的下一个结点的地址,赋给新创建结点的next 
    	head->next = node;          //  将新创建的结点的地址赋给头指针的下一个结点
    

    创建第一个结点

    执行第一次循环时,第一次从堆中开辟一块内存空间给node,此时需要做的是将第一个结点与 head 连接起来。而我们前面已经说过,单链表的最后一个结点指向的是 NULL

    因此插入第一个结点时,我们需要将头指针指向的 next 赋给新创建的结点的 next , 这样第一个插入的结点的 next 指向的就是 NULL。 接着,我们将数据域,也就是 node 的地址赋给 head->next, 这时 head->next 指向的就是新创建的 node的地址。而 node 指向的就是 NULL

    接着我们创建第二个结点

    因为使用的头插法,因此新开辟的内存空间需要插入 头指针所指向的下一个地址,也就是新开辟的 node 需要插入 上一个 nodehead 之间。 第一个结点创建之后,head->next 的地址是 第一个 node 的地址。 而我们申请到新的一块存储区域后,需要将 node->next 指向 上一个结点的首地址, 而新node 的地址则赋给 head->next。 因此也就是 node->next = head->next
    这样便将第一个结点的地址赋给了新创建地址的 next 所指向的地址。后两个结点就连接起来。

    接下来再将头结点的 next 所指向的地址赋为 新创建 node 的地址。 head->next = node ,这样就将头结点与新创建的结点连接了起来。 此时最后一个结点,也就是第一次创建的结点的数据域为0,指针域为 NULL

    创建更多的结点也就不难理解。
    执行一次:
    在这里插入图片描述

    会发现,头插法创建链表时候,就相当于后来居上。 后面的结点不断往前插,而最后创建的结点在第一个结点处, 第一个创建的结点变成了尾结点。

    尾插法创建单链表

    在这里插入图片描述

    尾插法代码:

    Linklist Creat_list(Linklist head) {
    	head = (Linklist)malloc(sizeof(Lnode));          //  为头指针开辟内存空间
    	Linklist node = NULL;           //  定义结点
    	Linklist end = NULL;            //  定义尾结点
    	head->next = NULL;              //  初始化头结点指向的下一个地址为 NULL
    	end = head;                     //  未创建其余结点之前,只有一个头结点
    	int count = 0 ;                 //  结点个数
    	printf("Input node number: ");
    	scanf("%d", &count);
    	for (int i = 0; i < count; i++) {
    		node = (Linklist)malloc(sizeof(Lnode));          //  为新结点开辟新内存
    		node->data = i;                                  //  新结点的数据域赋值
    		end->next = node;                      		
    		end = node;
    	}
    	end->next = NULL;
    }
    

    尾插法深刻理解:

    end->next = node;                      		
    end = node;
    

    尾插法创建第一个结点

    刚开始为头结点开辟内存空间,因为此时除过头结点没有新的结点的建立,接着将头结点的指针域 head->next 的地址赋为 NULL。因此此时,整个链表只有一个头结点有效,因此 head此时既是头结点,又是尾结点。因此将头结点的地址赋给尾结点 end 因此:end = head。 此时end 就是 head, head 就是 endend->next 也自然指向的是 NULL

    尾插法创建第二个结点

    创建完第一个结点之后,我们入手创建第二个结点。 第一个结点,endhead 共用一块内存空间。现在从堆中心开辟出一块内存给 node,将 node 的数据域赋值后,此时 end 中存储的地址是 head 的地址。此时,end->next 代表的是头结点的指针域,因此 end->next = node 代表的就是将上一个,也就是新开辟的 node 的地址赋给 head 的下一个结点地址。

    此时,end->next 的地址是新创建的 node 的地址,而此时 end 的地址还是 head 的地址。 因此 end = node ,这条作用就是将新建的结点 node 的地址赋给尾结点 end。 此时 end 的地址不再是头结点,而是新建的结点 node

    一句话,相当于不断开创新的结点,然后不断将新的结点的地址当做尾结点。尾结点不断后移,而新创的结点时按照创建的先后顺序而连接的。先来新到。

    尾插法创建单链表,结点创建完毕

    最后,当结点创建完毕,最后不会有新的结点来替换 end ,因此最后需要加上一条 end->next = NULL。将尾指针的指向为 NULL

    创建更多结点也自然容易理解了一些。

    执行一次:
    在这里插入图片描述

    总结

    由上面的例子以及比较,我们可以看见:

    1. 头插法相对简便,但插入的数据与插入的顺序相反;
    2. 尾插法操作相对复杂,但插入的数据与插入顺序相同。

    两种创建的方法各有千秋,根据实际情况选择不同的方法。

    关于链表的相关其他操作,请浏览相关文档。

    展开全文
  • 单链表_单链表_源码

    2021-10-01 16:29:29
    一个简单的单链表,具有插入删除打印等功能
  • 单链表的就地逆置

    万次阅读 多人点赞 2016-11-07 17:05:54
    单链表的就地逆置是指辅助空间O(1)的逆置方法,有两种方法:普通循环(头插法重新建立带头节点的新链表)和递归。下面我们详细介绍这两种方法:方法一:头插法算法思想:逆置链表初始为空,表中节点从原链表中依次...

    单链表的就地逆置是指辅助空间O(1)的逆置方法,有两种方法:普通循环(头插法重新建立带头节点的新链表)和递归。下面我们详细介绍这两种方法:

    方法一:头插法

    算法思想:逆置链表初始为空,表中节点从原链表中依次“删除”,再逐个插入逆置链表的表头(即“头插”到逆置链表中),使它成为逆置链表的“新”的第一个结点,如此循环,直至原链表为空。

    void converse(LinkList *head)
    {
    	LinkList *p,*q;
    	p=head->next;
        head->next=NULL;
    	while(p)
    	{
    		/*向后挪动一个位置*/
    		q=p;
    		p=p->next;
    		
    		/*头插*/
    		q->next=head->next;
    		head->next=q;
    	}
    }


    头插法图解:



    补充:

    对于不含头结点的单链表的头插法原地逆置

    ListNode* converse(ListNode *head)
    {
    	ListNode* dumyOfInsertedList = new ListNode(-1);//一个哑结点,用于创建新的链表
    	if(head == NULL) return NULL;
    	
    	ListNode* unInsertedHead = head;// 使用unInsertedHead和inInsertHead_next作为待逆置链表的首结点和次首结点的便签
    	ListNode* unInsertedHead_next = head->next;
    
    	while(unInsertedHead)// 头插直到原链表为空
    	{
    		unInsertedHead->next = dumyOfInsertedList->next;
    		dumyOfInsertedList->next = unInsertedHead;
    
    		unInsertedHead = unInsertedHead_next;
    		if(unInsertedHead_next!=NULL)// 注意:最后一个结点时,unInsertedHead_next为NULL没有next成员变量 
    		{
    			//cout<<"head:"<< unInsertedHead->val<<"next:"<<unInsertedHead_next->val<<endl;
    			unInsertedHead_next = unInsertedHead_next->next;
    		}
    	}
     
    	return dumyOfInsertedList->next;
    }

    方法二:递归

    算法思想:先假定有一个函数,可以将以head为头结点的单链表逆序,并返回新的头结点。利用这个函数对问题进行求解:将链表分为当前表头结点和其余部分,递归的过程就是,先将表头结点从链表中拆出来,然后对其余部分进行逆序,最后将当前的表头结点链接到逆序链表的尾部。递归的终止条件就是链表只剩一个节点时,直接返回这个节点。


    /*
    dfs深度遍历这个单链表
    在递归的时候,不作处理
    在回溯时,标记回溯开始的位置(新的头结点),将节点和节点的下一节点逆置,将新的头结点传递给上一层递归,
    接下来逆置上一个节点和上一节点的下一个节点(逆置已逆置链表的尾节点),并传递标记的头结点,直到回溯完成
    我们就得到了逆转的单链表和它的头结点
    dfs(当前状态)
    {
        if(边界状态)   //head==NULL说明链表为空,不用处理, 从头到尾我们需要处理的最后一个节点是倒数第二个节点,将它和倒数第一逆置,因此,遍历到倒是第一个节点就是边界条件
        {
           记录       //标记头结点位置并传递(这里选用返回值,还可以通过全局变量)给上一层递归
        }
        dfs(下一状态) 
        //回溯部分    //节点和下一节点(逆置这已逆置链表的尾结点和),将新的头结点传递给上一层递归
    }
    */
    ListNode *reverse(ListNode *head)
    {
        if(head==NULL || head->next ==NULL)
            return head;
    
        /*递归*/
        ListNode* headOfReverse = reverse(head->next);
        // cout<<head->next<<" "<<headOfReverse<<endl;
    
        /*回溯:将当前表头结点链接到逆序链表的尾部*/
        head->next->next = head;
        head->next = NULL;
        return headOfReverse;
    }
    递归法图解:




    参考:http://blog.csdn.net/lycnjupt/article/details/47103433


    展开全文
  • Java基础--单链表的实现

    万次阅读 多人点赞 2019-03-25 20:57:42
    Java内部也有自己的链表--LinkedList,但是我们今天不是讨论LinkedList,而是自己来实现一个单链表,包括简单的增删查改,以及使用链表来实现栈和队列这两种数据结构,涉及的方面如下: 单链表的结构 单链表的...

    Java内部也有自己的链表--LinkedList,但是我们今天不是讨论LinkedList,而是自己来实现一个单链表,包括简单的增删查改:

    • 单链表的结构
    • 单链表的基本操作
    • 虚拟头结点的使用

    整个类的设计如下:

    public class Linked <T>{
    	
    	private class Node{
    		private T t;
    		private Node next;
    		public Node(T t,Node next){
    			this.t = t;
    			this.next = next;
    		}
    		public Node(T t){
    			this(t,null);
    		}
    	}
    	private Node head;    		//头结点
    	private int size;			//链表元素个数
    	//构造函数
    	public Linked(){
    		this.head = null;
    		this.size = 0;
    	}
    }
    

    单链表的结构

    一种链式存取的数据结构,单链表中的数据是以结点的形式存在,每一个结点是由数据元素和下一个结点的存储的位置组成。单链表与数组相比的最大差别是:单链表的数据元素存放在内存空间的地址是不连续的,而数组的数据元素存放的地址在内存空间中是连续的,这也是为什么根据索引无法像数组那样直接就能查询到数据元素。

    [单链表结构图]

    链表存储的结点

    private class Node{
    		private T t;
    		private Node next;
    		public Node(T t,Node next){
    			this.t = t;
    			this.next = next;
    		}
    		public Node(T t){
    			this(t,null);
    		}
    }
    

    链表的基本操作

    包括链表的增删查改,以及判别某结点是否存在链表中

    链表结点的增加

    进行结点的添加的时候,是根据索引来进行操作的,由于成员变量size记录了当前链表的元素个数,进行某个索引位置的结点插入就会很方便了。先找到该目标索引的前一个结点,记录为pre,把要插入的结点node的下一个结点node.next指向pre的下一个结点pre.next;再把pre.next指向node结点。如果先进行pre.next指向要插入的结点,再进行node.next指向pre.next的话,无疑是要插入的结点自己指向了自己,无法连接上整个链表,在链表的操作中,有时候顺序的执行会带来不一样的结果。

    //链表头部添加元素
    	public void addFirst(T t){
    		Node node = new Node(t);	//节点对象
    		node.next = this.head;
    		this.head = node;
    		//this.head = new Node(e,head);等价上述代码
    		this.size++;
    	}
    	//向链表尾部插入元素
    	public void addLast(T t){
    		this.add(t, this.size);
    	}
    	//向链表中间插入元素
    	public void add(T t,int index){
    		if (index <0 || index >size){
    			throw new IllegalArgumentException("index is error");
    		}
    		if (index == 0){
    			this.addFirst(t);
    			return;
    		}
    		Node preNode = this.head;
    		//找到要插入节点的前一个节点
    		for(int i = 0; i < index-1; i++){
    			preNode = preNode.next;
    		}
    		Node node = new Node(t);
    		//要插入的节点的下一个节点指向preNode节点的下一个节点
    		node.next = preNode.next;
    		//preNode的下一个节点指向要插入节点node
    		preNode.next = node;
    		this.size++;
    	}
    

    链表结点的删除

    //删除链表元素
    	public void remove(T t){
    		if(head == null){
    			System.out.println("无元素可删除");
    			return;
    		}
    		//要删除的元素与头结点的元素相同
    		while(head != null && head.t.equals(t)){
    			head = head.next;
    			this.size--;
    		}
    		/**
    		 * 上面已经对头节点判别是否要进行删除
    		 * 所以要对头结点的下一个结点进行判别
    		 */
    		Node cur = this.head;
    		while(cur != null && cur.next != null){
    			if(cur.next.t.equals(t)){
    				this.size--;
    				cur.next = cur.next.next;
    			}
    			else cur = cur.next;
    		}
    		
    	}
    

    在进行链表的结点删除时候,要分情况讨论:

    当要删除的结点位于头结点的时候: 如下图要删除的元素1的结点位于头结点,先进行while判断头结点是否为null且判断该结点的元素是否为要删除的元素,如果是把head指向head.next即可,直接跳过头结点,直到头结点不是要删除的元素就结束循环。

    [要删除的元素1位于头结点]

    当要删除的结点不在头结点的时候:如下图删除元素为3的结点,由于上面已经判断了头结点不是要删除的元素,所以我们从头结点的下一个结点开始循环,即cur.next,当cur.next是要被删除的元素时,直接cur.next = curr.next.next就能直接跳过cur.next,断开。
    [要删除结点的元素为3的结点]

    删除链表的头结点的元素和删除链表的尾结点的元素

    //删除链表第一个元素
    	public T removeFirst(){
    		if(this.head == null){
    			System.out.println("无元素可删除");
    			return null;
    		}
    		Node delNode = this.head;
    		this.head = this.head.next;
    		delNode.next =null;
    		this.size--;
    		return delNode.t;
    	}
    	//删除链表的最后一个元素
    	public T removeLast(){
    		if(this.head == null){
    			System.out.println("无元素可删除");
    			return null;
    		}
    		//只有一个元素
    		if(this.getSize() == 1){
    			return this.removeFirst();
    		}
    		Node cur = this.head;	//记录当前结点
    		Node pre = this.head;	//记录要删除结点的前一个结点
    		while(cur.next != null){
    			pre = cur;
    			cur = cur.next;
    		}
    		pre.next = cur.next;
    		this.size--;
    		return cur.t;
    	}
    

    经过上面在进行链表的结点删除的时候,会发现在删除的过程中很麻烦,还得考虑头结点(因为我们在删除结点的时候,都是先找到待删除结点del的前一个结点pre,然后直接进行跳过操作,即pre.next = pre.next.next,但是删除结点头结点的时候就无法操作),给我们添加了麻烦,为此我们可以给链表添加一个虚拟的头结点,说白了就是重新new一个结点对象,该结点对象的下一个结点指向了我们之前的头结点,让我们在删除结点的时候,无须再考虑之前的头结点了!

    虚拟头结点删除链表元素的实现

    //加入虚拟头结点的链表进行删除
    	public void removeElt(T t){
    		//构造虚拟头结点,并且下一个结点指向head
    		Node dummy = new Node(t,this.head);
    		//声明结点指向虚拟头结点
    		Node cur = dummy;
    		//从虚拟头结点的下一个结点开始遍历
    		while(cur.next != null){
    			if(cur.next.t.equals(t)){ 
    				cur.next = cur.next.next;
    				this.size--;
    			}
    			else cur = cur.next;
    		}
    		//去除虚拟头结点
    		this.head = dummy.next;
    	}
    

    使用虚拟头结点进行链表的插入

    刚开始那部分的结点添加是基于索引的情况实现,当我们无法知道一个结点的位于链表的哪个位置时候,只知道要插入在某个元素的前面,下面的代码基于上述情况实现。

    	/**
    	 * 
    	 * @param t:插入在t元素的位置
    	 * @param des:要插入的元素
    	 */
    	public void insert(T t,T des){
    		//构造虚拟头结点,并且下一个结点指向head
    		Node dummy = new Node(null,this.head);
    		//构造要插入的结点
    		Node dNode = new Node(des);
    		//声明变量cur指向虚拟头结点
    		Node cur = dummy;
    		while(cur.next != null){
    			if(cur.next.t.equals(t)){ 
    				dNode.next = cur.next;
    				cur.next = dNode;
    				this.size++;
    				break;
    			}
    			else cur = cur.next;
    		}
    		this.head = dummy.next;
    	}
    

    查找某个元素是否在链表的结点上

    //链表中是否包含某个元素
    	public boolean contains(T t){
    		Node cur = this.head;
    		while(cur != null){
    			if(cur.t.equals(t)){
    				return true;
    			}
    			else cur = cur.next;
    		}
    		return false;
    	}
    

    完整的代码实现:

    package LinkedList;
    
    public class Linked <T>{
    	
    	private class Node{
    		private T t;
    		private Node next;
    		public Node(T t,Node next){
    			this.t = t;
    			this.next = next;
    		}
    		public Node(T t){
    			this(t,null);
    		}
    	}
    	private Node head;    		//头结点
    	private int size;			//链表元素个数
    	//构造函数
    	public Linked(){
    		this.head = null;
    		this.size = 0;
    	}
    	
    	//获取链表元素的个数
    	public int getSize(){
    		return this.size;
    	}
    	//判断链表是否为空
    	public boolean isEmpty(){
    		return this.size == 0;
    	}
    	//链表头部添加元素
    	public void addFirst(T t){
    		Node node = new Node(t);	//节点对象
    		node.next = this.head;
    		this.head = node;
    		// this.head = new Node(e,head);等价上述代码
    		this.size++;
    	}
    	//向链表尾部插入元素
    	public void addLast(T t){
    		this.add(t, this.size);
    	}
    	//向链表中间插入元素
    	public void add(T t,int index){
    		if (index <0 || index >size){
    			throw new IllegalArgumentException("index is error");
    		}
    		if (index == 0){
    			this.addFirst(t);
    			return;
    		}
    		Node preNode = this.head;
    		//找到要插入节点的前一个节点
    		for(int i = 0; i < index-1; i++){
    			preNode = preNode.next;
    		}
    		Node node = new Node(t);
    		//要插入的节点的下一个节点指向preNode节点的下一个节点
    		node.next = preNode.next;
    		//preNode的下一个节点指向要插入节点node
    		preNode.next = node;
    		this.size++;
    	}
    	//删除链表元素
    	public void remove(T t){
    		if(head == null){
    			System.out.println("无元素可删除");
    			return;
    		}
    		//要删除的元素与头结点的元素相同
    		while(head != null && head.t.equals(t)){
    			head = head.next;
    			this.size--;
    		}
    		/**
    		 * 上面已经对头节点判别是否要进行删除
    		 * 所以要对头结点的下一个结点进行判别
    		 */
    		Node cur = this.head;
    		while(cur != null && cur.next != null){
    			if(cur.next.t.equals(t)){
    				this.size--;
    				cur.next = cur.next.next;
    			}
    			else cur = cur.next;
    		}
    		
    	}
    	//删除链表第一个元素
    	public T removeFirst(){
    		if(this.head == null){
    			System.out.println("无元素可删除");
    			return null;
    		}
    		Node delNode = this.head;
    		this.head = this.head.next;
    		delNode.next =null;
    		this.size--;
    		return delNode.t;
    	}
    	//删除链表的最后一个元素
    	public T removeLast(){
    		if(this.head == null){
    			System.out.println("无元素可删除");
    			return null;
    		}
    		//只有一个元素
    		if(this.getSize() == 1){
    			return this.removeFirst();
    		}
    		Node cur = this.head;	//记录当前结点
    		Node pre = this.head;	//记录要删除结点的前一个结点
    		while(cur.next != null){
    			pre = cur;
    			cur = cur.next;
    		}
    		pre.next = cur.next;
    		this.size--;
    		return cur.t;
    	}
    	//链表中是否包含某个元素
    	public boolean contains(T t){
    		Node cur = this.head;
    		while(cur != null){
    			if(cur.t.equals(t)){
    				return true;
    			}
    			else cur = cur.next;
    		}
    		return false;
    	}
    	@Override
    	public String toString() {
    		StringBuffer sb = new StringBuffer();
    		Node cur = this.head;
    		while(cur != null){
    			sb.append(cur.t+"->");
    			cur = cur.next;
    		}
    		sb.append("NULL");
    		return sb.toString();
    	}
    	
    	public static void main(String[] args) {
    		Linked<Integer> linked = new Linked();
    		for(int i = 0; i < 10; i++){
    			linked.addFirst(i);
    			System.out.println(linked);
    		}
    		linked.addLast(33);
    		linked.addFirst(33);
    		linked.add(33, 5);
    		System.out.println(linked);
    		linked.remove(33);
    		System.out.println(linked);
    		System.out.println("删除第一个元素:"+linked.removeFirst());
    		System.out.println(linked);
    		System.out.println("删除最后一个元素:"+linked.removeLast());
    		System.out.println(linked);
    	}
    }
    
    

    总结:学链表是一种痛苦,但是痛苦并快乐着,希望能够坚持下去,把链表的全家桶都学习了,而不是这么简单的增加和删除。上述如有说的不对的地方欢迎指正!下篇文章将进行用链表实现栈和队列。

    展开全文
  • 典型的c语言数据结构单链表
  • 合并单链表

    2016-09-16 11:24:38
    合并单链表
  • 无环单链表+有环单链表or有环单链表+无环单链表 判断相交 必定不相交
  • 单链表逆序

    2016-03-04 17:59:53
    单链表逆序 步骤: 1. 初始化单链表 2. 动态创建单链表(插入操作) 3. 逆序算法处理 4. 打印输出 5. 释放动态创建的单链表
  • 单链表C++实现代码

    万次阅读 多人点赞 2019-06-20 16:01:28
    因为没什么事做就写一下单链表的操作,反正是基础数据结构,长时间不写的话再写会出现一下小的细节毛病,多练习练习,理解也更加深点。 单链表写顺,队列的入队出队就是单链表的头插和尾删而已,栈的入栈出栈就是...
  • 单链表实现

    2017-02-24 23:29:09
    单链表实现
  • 单链表之排序单链表

    千次阅读 2018-05-08 19:45:23
    package list; public class SortedSinglyList&lt;T extends Comparable&lt;? super T&gt;&gt; extends SinglyList { ... * 构造空排序单链表 ... // 直接调用单链表的构造方法,构造一个空的单链表 ...
  • 单链表的操作

    2019-03-07 10:19:53
    1)编程实现单链表的以下基本操作:建立单链表,查找单链表,插入单链表,删除单链表。 2)采用单链表结构编程实现:两个有序单链表的归并运算。
  • C语言之单链表初始化

    千次阅读 多人点赞 2020-04-26 23:04:44
    单链表
  • 通过冒泡排序进行单链表的有序插入,并将这两个有序单链表合并成一个有序单链表,使用两个单链表的原有空间进行合并,将生成的有序单链表输出显示
  • 建立单链表

    2014-11-26 17:04:43
    单链表的建立,建立单链表节点,建立简单链表
  • 完成单链表的最基本操作,包括单链表的插入、删除等基本操作。有良好的界面,调试运行没问题。
  • 数据结构-单链表基本操作-C语言代码

    万次阅读 多人点赞 2020-01-22 19:51:58
    单链表基本操作 1.头插法建立单链表 2.尾插法建立单链表 3.查找结点 3.修改结点 4.插入结点 5.删除结点 本篇只有c语言代码,具体思路讲解请看这篇博客:数据结构-线性结构-单链表 1.头插法建立单链表 #include<...
  • 静态单链表

    2011-09-26 22:59:22
    静态单链表静态单链表静态单链表静态单链表静态单链表
  • 单链表操作

    2016-11-12 20:41:36
    单链表的初始化,插入删除释放......
  • 关于单链表

    2021-04-07 10:38:56
    基础知识:什么是单链表,链式存储结构详解 单链表 基础操作:单链表的基本操作(C语言版) 最后附加一篇大佬的文章 【C语言】链表及单链表基本操作
  • 创建单链表并输出单链表

    千次阅读 2020-07-19 11:36:43
    创建一个单链表并输出单链表 ①基本思路: 定义一个结构体,包含数据域和指针域,前者为该结点保存的用户数据,后者为该结点保存的下一个相邻结点的地址。 定义一个结点创建函数(返回head),用head指向第一个结点、...
  • 单链表.c

    2021-09-03 11:20:49
    单链表.c

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 161,332
精华内容 64,532
关键字:

单链表