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

    2020-04-22 21:12:56
    一、单链表简述 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素+ 指针,元素就是存储数据的存储单元,指针就是连接每个...

    一、单链表简述

    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素+ 指针,元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

    1、单链表的定义
    链表是通过一组地址任意的存储单元来存储线性表中的数据元素,这些存储单元可以是连续的,也可以是不连续的。

    2、单链表的特点
    逻辑相邻的数据元素其物理存储位置不一定相邻。为表示数据元素之间的线性关系,在存储数据元素时,除了要存放数据元素自身的信息外,还要额外存放一个其直接后继的存储地址。

    3、图解单链表
    在这里插入图片描述

    二、单链表

    #pragma once
    
    typedef int ElemType;
    
    typedef struct Node
    {
    	union
    	{
    		int length;
    		ElemType data;
    	};
    
    	struct Node *next;
    }LNode, *LinkList;
    
    void InitLinkList(LinkList list);
    
    int InsertLinkListPos(LinkList list, ElemType val, int pos);
    int InsertLinkListHead(LinkList list, ElemType val);
    int InsertLinkListTail(LinkList list, ElemType val);
    
    void ShowLinkList(LinkList list);
    
    int DeleteLinkListPos(LinkList list, int pos);
    int DeleteLinkListHead(LinkList list);
    int DeleteLinkListTail(LinkList list);
    
    void ClearLinkList(LinkList list);
    void DestoryLinkList(LinkList list);
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include "List.h"
    
    //判断链表是否为空
    static void DeterPointIsNULL(LinkList list)
    {
    	assert(list != NULL);
    	if (list == NULL)
    	{
    		printf("list is NULL, Please Check\n");
    		exit(0);
    	}
    }
    
    //申请一个新节点
    static LinkList _ApplyNode(ElemType val, LinkList point)
    {
    	LinkList s = (LinkList)malloc(sizeof(LNode));
    	assert(s != NULL);
    
    	s->data = val;
    	s->next = point;
    
    	return s;
    }
    
    //初始化一个单链表
    void InitLinkList(LinkList list)
    {
    	DeterPointIsNULL(list);
    
    	list->length = 0;
    	list->next = NULL;
    }
    
    //插入
    int InsertLinkListPos(LinkList list, ElemType val, int pos)
    {
    	DeterPointIsNULL(list);
    
    	if (pos < 0 || pos > list->length)
    	{
    		printf("pos is out of range, Insert fail\n");
    		return 0;
    	}
    
    	LinkList p = list;
    
    	while (pos > 0)
    	{
    		p = p->next;
    		pos--;
    	}
    
    	p->next = _ApplyNode(val, p->next);
    
    	return 1;
    }
    
    int InsertLinkListHead(LinkList list, ElemType val)
    {
    	return InsertLinkListPos(list, val, 0);
    }
    
    int InsertLinkListTail(LinkList list, ElemType val)
    {
    	DeterPointIsNULL(list);
    
    	return InsertLinkListPos(list, val, list->length);
    }
    
    //打印
    void ShowLinkList(LinkList list)
    {
    	DeterPointIsNULL(list);
    
    	LinkList p = list->next;
    
    	while (p)
    	{
    		printf("%d ", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    //删除
    int DeleteLinkListPos(LinkList list, int pos)
    {
    	DeterPointIsNULL(list);
    
    	if (pos < 0 || pos >= list->length)
    	{
    		printf("pos is out of range, Insert fail\n");
    		return 0;
    	}
    
    	LinkList p = list;
    
    	while (pos > 0)
    	{
    		p = p->next;
    		pos--;
    	}
    
    	LinkList q = p->next;
    	p->next = q->next;
    	free(q);
    
    	list->length--;
    
    	return 1;
    }
    int DeleteLinkListHead(LinkList list)
    {
    	return DeleteLinkListPos(list, 0);
    }
    
    int DeleteLinkListTail(LinkList list)
    {
    	DeterPointIsNULL(list);
    
    	return DeleteLinkListPos(list, list->length - 1);
    }
    
    //清空和销毁
    void ClearLinkList(LinkList list)
    {
    	DestoryLinkList(list);
    }
    
    void DestoryLinkList(LinkList list)
    {
    	DeterPointIsNULL(list);
    
    	while (list->next != NULL)
    	{
    		DeleteLinkListHead(list);
    	}
    }
    

    三、单链表的应用

    1、判断两个单链表是否相交并返回第一个交点

    解析:按照单链表的构成来说,两个单链表相交的条件是两个单链表中有一个结点数据元素相等,存储的下一个元素地址相同,如下图所示:
    在这里插入图片描述

    可以发现,当两个单链表相交时,其后面的结点也一定相等,即可以转化为当两个单链表剩余结点数相等时,同时向后进行移动,相等的结点即为两个单链表第一个相交的结点。

    代码:

    //相交并返回第一个交点
    LinkList IntersectLinkList(LinkList list1, LinkList list2)
    {
    	DeterPointIsNULL(list1);
    	DeterPointIsNULL(list2);
    
    	int len1 = list1->length;
    	int len2 = list2->length;
    
    	LinkList p = list1;
    	LinkList q = list2;
    
    	if (len1 > len2)
    	{
    		for (int i = 0; i < len1; ++i)
    		{
    			p = p->next;
    		}
    	}
    	if (len1 < len2)
    	{
    		for (int i = 0; i < len2; ++i)
    		{
    			q = q->next;
    		}
    	}
    
    	while (p)
    	{
    		if (p == q)
    		{
    			return p;
    		}
    
    		p = p->next;
    		q = q->next;
    	}
    
    	return NULL;
    }
    

    2、判断单链表是否有环

    解析:单链表根据其特点,一旦有环就不会出环,这里可以运用快慢指针来做,下面画图来说明:
    在这里插入图片描述

    代码:

    //判断是否有环并返回交点
    static LinkList RingList(LinkList list)
    {
    	LinkList p = list, q = list;
    
    	while (q != NULL)
    	{
    		p = p->next;
    		q = q->next;
    		if (q == NULL)
    		{
    			return NULL;
    		}
    		q = q->next;
    
    		if (p == q)
    		{
    			return p;
    		}
    	}
    
    	return NULL;
    }
    
    LinkList IsRingList(LinkList list)
    {
    	DeterPointIsNULL(list);
    
    	LinkList pNode = RingList(list);
    
    	LinkList qNode = list;
    
    	while (pNode != qNode)
    	{
    		pNode = pNode->next;
    		qNode = qNode->next;
    	}
    
    	return pNode;
    }
    

    3、在O(1)下删除一个结点p

    解析:由于单链表不能直接得知一个结点的前驱,所以一般采用的方法需要用到O(n)的时间复杂度。要在O(1)下完成,可以另辟新径,把后一个结点的数据值复制到需要删除的结点,然后删除后一个结点,下面画图:
    在这里插入图片描述

    代码:

    void DeleteLinkListNode(LinkList list,LinkList p)
    {
    	if (p == NULL || p->next == NULL)
    	{
    		return;
    	}
    
    	LinkList q = p->next;
    	p->data = q->data;
    	p->next = q->next;
    	free(q);
    }
    

    4、在O(1)下添加一个结点在结点p前面

    解析:这个的做法与上面类似,主要运用的方法还是向后操作,把新节点添加在后面,通过数据交换来达到向前添加结点的作用,如下图:

    在这里插入图片描述

    代码:

    void InsertOfNode(LinkList list, LinkList p, ElemType val)
    {
    	if (list == NULL || p == NULL || p == list)
    	{
    		return;
    	}
    
    	LinkList s = _ApplyNode(p->data, p->next);
    
    	p->data = val;
    	p->next = s;
    }
    

    5、逆置单链表

    解析:单链表逆置的其实很简单,只需要保证能依次拿到下一个指针并改变顺序即可,下面画图说明:

    在这里插入图片描述
    代码:

    void ResverLinkList(LinkList list)
    {
    	DeterPointIsNULL(list);
    
    	if (list->length < 2)
    	{
    		return;
    	}
    
    	LinkList s = NULL, p = list->next;
    	LinkList q = p->next;
    
    	while (p != NULL)
    	{
    		p->next = s;
    		s = p;
    		p = q;
    		if (q != NULL)
    		{
    			q = q->next;
    		}
    	}
    }
    
    展开全文
  • 创建单链表的头插法与尾插法详解

    万次阅读 多人点赞 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. 尾插法操作相对复杂,但插入的数据与插入顺序相同。

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

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

    展开全文
  • 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);
    	}
    }
    
    

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

    展开全文
  • 无环单链表+有环单链表or有环单链表+无环单链表 判断相交 必定不相交

    无环单链表+有环单链表or有环单链表+无环单链表

    • 判断相交
      必定不相交
      在这里插入图片描述
    展开全文
  • 单链表逆序

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

    千次阅读 多人点赞 2020-04-26 23:04:44
    单链表
  • 单链表之排序单链表

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

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

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

    2014-11-26 17:04:43
    单链表的建立,建立单链表节点,建立简单链表
  • 通过冒泡排序进行单链表的有序插入,并将这两个有序单链表合并成一个有序单链表,使用两个单链表的原有空间进行合并,将生成的有序单链表输出显示
  • 静态单链表

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

空空如也

1 2 3 4 5 ... 20
收藏数 62,149
精华内容 24,859
关键字:

单链表