单向链表 订阅
单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;链表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向NULL的指针。 展开全文
单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;链表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向NULL的指针。
信息
外文名
One-way LinkedList
定    义
链表的一种
特    点
链表的链接方向是单向的
中文名
单向链表
目    的
学习单向链表
单向链表链表的优点
相比较普通的线性结构,链表结构的可以总结一下: (1)单个结点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小(2)结点的删除非常方便,不需要像线性结构那样移动剩下的数据(3)结点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表
收起全文
精华内容
下载资源
问答
  • 单向链表

    2020-01-13 12:29:16
    文章目录单向链表基本概念单向链表的节点结构单向链表的操作构造单向链表节点单向链表的插入单向链表末尾插入单向链表有序插入 单向链表 基本概念   在基于指针的链式结构中,单向链表是最基本的。   在单向...

    单向链表

    基本概念

      在基于指针的链式结构中,单向链表是最基本的。
      在单向链表中,每个节点都有两个域,一个是用于存放数据元素的域element,一个用于指向后继节点的指针域link
    在这里插入图片描述
      单向链表的第一个节点称为起始节点,指向起始节点的指针称为头指针,头指针为NULL的单向链表称为空表
    在这里插入图片描述
      例如具有五个节点的单向链表结构如下:
    在这里插入图片描述

    单向链表的节点结构

      单向链表的每个节点的结构都具有跟如下定义相似的结构类型;

    typedef struct _node
    {
    	T element;
    	struct _node* link;
    }node;
    

      T element是数据域,可以是一个或多个基本类型的数据,也可以是结构体或者是联合;struct node* link是指针域,这是一个自引用的结构。

    单向链表的操作

    构造单向链表节点

      用malloc函数向堆中申请一块node大小的内存,元素element则采用传参的方式进行填充,如果申请成功则返回节点起始地址,申请失败则返回NULL

    node* nodeCreate(int element)
    {
    	node* ptr = (node*)malloc(sizeof(node));
    	if (ptr == NULL)
    	{
    		printf("内存分配失败\r\n");
    		return NULL;
    	}
    	printf("创建节点地址:%d\r\n", ptr);
    	ptr->element = element;
    	ptr->link = NULL;
    	return ptr;
    }
    

      代码中的node采用以下类型结构,即将T element;替换为具体的整形元素。

    typedef struct _node
    {
    	int element;
    	struct _node* link;
    }node;
    

    单向链表的插入

      单向链表的插入方式按照需求会有好几种方式,例如直接在链表末尾插入,或者按照element的大小有序进行插入。

    单向链表末尾插入

      如果不考虑节点中某些数据的有序性,直接在链表的末尾进行插入,这种方式会简单一些,省去了比较的过程。在创建一个节点后,直接从head开始往后寻找最后那个节点,然后把新建节点的起始地址给末尾节点的link,若headNULL,则直接把节点的起始地址给head
    在这里插入图片描述在这里插入图片描述  如果是非空链表,查找末尾节点的判定方式是判断link是否为NULL,即if(ptr->link==NULL);但是如果是空链表,判断方式则是if(head==NULL);这么一分析,似乎插入这一操作还得区别链表是否为空链表;这就有一个边缘情况,能否消除这种边缘情况,将两种情况下的操作统一起来。

    node* NodeInsertLast(list* head, node* n)
    {
    	list* ptr = head;
    	while (*ptr != NULL)
    	{
    		ptr = &(*ptr)->link;
    	}
    	*ptr = n;
    	return *head;
    }
    

      形参里面的listnode*类型,即形参中的head是指向node指针类型数据的指针。一般头指针变量的定义是这样的:node* head = NULL,若形参中的head类型为node*还会导致另一个问题,头指针无法以参数的方式传入NodeInsertLast

    单向链表有序插入

      有序插入时不仅会遇到末尾插入面临的两种情况,还会遇到头指针与起始节点之间插入和节点与节点之间插入的情况。
    在这里插入图片描述
    在这里插入图片描述  情况更复杂了吗?看起来更复杂了。
      如果在链表末尾插入,即当前链表所有节点中的element元素数值都要比n->element小的情况,与空表的情况,过程和NodeInsertLast函数是一致的,只不过多了n->link = *ptr;这个赋值过程,此时*ptr值为NULL
      在p节点和q节点之间插入一个节点,既要获得后继节点qelement的值,又不能丢失前驱节点p。第一种方法是定义两个node指针变量,一个用来指向p,一个用来指向q,两个指针同时向后移动,当比较后发现满足条件就在二者之间插入。有没有更简单的方法,像前文消除head特殊情况一样;而且这里也有边缘情况。

    node* NodeInsertOrder(list* head, node* n)
    {
    	list* ptr = head;
    	while (*ptr != NULL)
    	{
    		if ((*ptr)->element > n->element) 
    			break;
    		ptr = &(*ptr)->link;
    	}
    	n->link = *ptr;
    	*ptr = n;
    	return *head;
    }
    

      同样的,这里的head是指向node指针数据的指针,这就可以做到以参数的方式传递进来还可以修改头指针的指向。
      ((*ptr)->element > n->element)这条语句在访问后驱节点中element的情况下还保存了前驱节点的信息,即前驱节点link的地址。在发现后驱节点中element值要比n->element大,则跳出while,此时ptr存放的是前驱节点link的地址,所以可以做到在两个节点之间插入新节点,包括头指针和起始节点之间插入的情况。

    单向链表的删除

      链表节点的删除一般是根据element的情况来查找的,不可能不顾数据的有效性就删除某个节点。如果有那就是清空整个链表了。
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述  这三种情况也就是删除中间节点和边缘节点,节点的删除和插入其实是类似的,也可以消除边缘情况,用一个函数解决。

    void NodeDelete(list* head, int element)
    {
    	list* ptr = head;
    	node* free_ptr = NULL;
    	while (*ptr != NULL)
    	{
    		if ((*ptr)->element == element)
    		{
    			free_ptr = *ptr;
    			*ptr = (*ptr)->link;
    			free(free_ptr);
    			printf("释放节点地址:%d\r\n", free_ptr);
    			return;
    		}
    		ptr = &(*ptr)->link;
    	}
    	printf("没有element值为%d的节点!\r\n",element);
    }
    

      节点的删除操作就不能像节点插入那样用一个变量解决了,需要free_ptr进行暂存。如果没有这个中间变量,会出现什么情况:

    1. 先释放节点,这时就会丢失释放节点的后继节点起始地址。
    2. 先把释放节点的后继节点起始地址给释放节点的前驱节点则会丢失释放节点的起始地址(比较绕)。

    单向链表的清空

      当一个链表不需要的时候如何一次性清空所有节点,用NodeDelete函数进行一个节点一个节点释放效率就低了,而且element的值是可以改变的,甚至都不知道此时链表节点的element都有哪些值,直接把NULLhead就更不行了。

    void NodeClear(list* head)
    {
    	node* ptr = NULL;
    	while (*head)
    	{
    		ptr = (*head)->link;
    		printf("释放节点地址:%d\r\n", *head);
    		free(*head);
    		*head = ptr;
    	}
    }
    

      这个函数的操作过程是将链表从起始节点开始一个节点一个节点释放,最后将末尾节点的link值(NULL)给了头指针。函数形参如果定义为node*而不是list*,则清空函数无法改变头指针的值。当清空函数退出时,头指针仍指向原起始节点所在的起始地址,这个时候是非常危险的,一旦忘记清空头指针,则会访问一段已经释放了的内存。

    单向链表的输出

      最后为了直观的查看链表的情况,可以实现一个链表输出函数。

    void ListPrintf(node* head)
    {
    	node* ptr = head;
    	while (ptr != NULL)
    	{
    		printf("element:%d\r\n", ptr->element);
    		ptr = ptr->link;
    	}
    }
    

      链表的输出只是进行访问,不进行修改,更不会修改头指针指向,所以形参可以直接传入头指针的值,而不是头指针的地址。

    源代码

      突然发现MarkDown格式没有哪里可以上传文件,那只能把源码贴出来。

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct _node
    {
    	int element;
    	struct _node* link;
    }node;
    typedef node* list;
    
    node* NodeCreate(int element)
    {
    	node* ptr = (node*)malloc(sizeof(node));
    	if (ptr == NULL)
    	{
    		printf("内存分配失败\r\n");
    		return NULL;
    	}
    	printf("创建节点地址:%d\r\n", ptr);
    	ptr->element = element;
    	ptr->link = NULL;
    	return ptr;
    }
    
    node* NodeInsertLast(list* head, node* n)
    {
    	list* ptr = head;
    	while (*ptr != NULL)
    	{
    		ptr = &(*ptr)->link;
    	}
    	*ptr = n;
    	return *head;
    }
    
    node* NodeInsertOrder(list* head, node* n)
    {
    	list* ptr = head;
    	while (*ptr != NULL)
    	{
    		if ((*ptr)->element > n->element) 
    			break;
    		ptr = &(*ptr)->link;
    	}
    	n->link = *ptr;
    	*ptr = n;
    	return *head;
    }
    
    void NodeDelete(list* head, int element)
    {
    	list* ptr = head;
    	node* free_ptr = NULL;
    	while (*ptr != NULL)
    	{
    		if ((*ptr)->element == element)
    		{
    			free_ptr = *ptr;
    			*ptr = (*ptr)->link;
    			free(free_ptr);
    			printf("释放节点地址:%d\r\n", free_ptr);
    			return;
    		}
    		ptr = &(*ptr)->link;
    	}
    	printf("没有element值为%d的节点!\r\n",element);
    }
    
    void NodeClear(list* head)
    {
    	node* ptr = NULL;
    	while (*head)
    	{
    		ptr = (*head)->link;
    		printf("释放节点地址:%d\r\n", *head);
    		free(*head);
    		*head = ptr;
    	}
    }
    
    void ListPrintf(node* head)
    {
    	node* ptr = head;
    	while (ptr != NULL)
    	{
    		printf("element:%d\r\n", ptr->element);
    		ptr = ptr->link;
    	}
    }
    
    int main()
    {
    	node* head = NULL;
    	node* p = NULL;
    	for (size_t i = 1; i < 10; i+=2)
    	{
    		p = NodeCreate(i);
    		if (p != NULL)
    			NodeInsertLast(&head, p);
    	}
    	for (size_t i = 0; i < 10; i += 2)
    	{
    		p = NodeCreate(i);
    		if (p != NULL)
    			NodeInsertOrder(&head, p);
    	}
    	NodeDelete(&head, 0);
    	NodeDelete(&head, 1);
    	NodeDelete(&head, 2);
    	NodeDelete(&head, 3);
    	NodeDelete(&head, 4);
    	NodeDelete(&head, 9);
    	NodeDelete(&head, 9);
    	NodeDelete(&head,10);
    	ListPrintf(head);
    	NodeClear(&head);
    	if (head == NULL)
    		printf("链表节点内存全部释放\r\n");
    	while (1);
    }
    

    运行结果如图
    在这里插入图片描述

    展开全文
  • C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表
  • c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,c++实现单向链表逆转,
  • 04.单向链表以及单向链表的应用.ppt
  • 单向链表反转先创建一个单向链表/*** 单向链表 * * */class Node{public Node(int value){this.value = value;}public int value;public Node next;}头插法头插法使用双指针方式进行头插/*** 方式1 * @param head* @...

    单向链表反转

    先创建一个单向链表/**

    * 单向链表 * * */class Node{

    public Node(int value){

    this.value = value;

    }

    public int value;

    public Node next;

    }头插法

    头插法使用双指针方式进行头插/**

    * 方式1 * @param head

    * @return

    */

    public static Node reverse1(Node head){

    /**

    * 判断当前节点是否为空或者仅有一个节点

    */

    if (head == null || head.next == null) {

    return head;

    }

    //记录上一个cur的节点

    Node pre = null;

    //记录当前节点的下一个节点

    Node post;

    while (head!=null){

    //把post节点前移

    post = head.next;

    //当前节点的下一个节点指向上一次的当前节点

    head.next = pre;

    //把当前节点赋值给pre,用于下次使用

    pre = head;

    //把当前节点前移

    head = post;

    }

    //由于最后循环中 head = post已经做了前移,所以此处取pre为反转后的链表

    return pre;

    }递归反转/**

    * 方式2,递归 * @param head

    * @return

    */

    public static Node reverse2(Node head){

    /**

    * 判断当前节点是否为空或者仅有一个节点

    */

    if (head == null || head.next == null) {

    return head;

    }

    /**

    * 递归方式获取下一个节点,最底层返回的node为链表的尾部

    */

    Node node = reverse2(head.next);

    /**

    * 此处进行反转

    */

    head.next.next = head;

    head.next = null;

    return node;

    }

    展开全文
  • 链表单向链表单向链表概念链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。这是一种物理结构,不是树那样的逻辑结构。链表和顺序表两种物理结构,说明的是...

    链表

    单向链表

    单向链表概念

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

    这是一种物理结构,不是树那样的逻辑结构。链表和顺序表两种物理结构,说明的是数据元素在内存中是如何存储的。顺序表是连续顺序存储,例如数组。而链表是非连续非顺序的。

    基本API的java代码实现

    代码如下,实现基本的增查删改的功能。public class SinglyLinkedList {

    288eae6aca9cde9f5b7351abdace88ab.png

    各个API的时间复杂度O(n)

    接下来分析时间复杂度

    Singly-Linked Listno tailwith tail

    PushFront(key)

    O(1)

    TopFront()

    O(1)

    PopFront()

    O(1)

    PushBack(key)

    O(n)

    O(1)

    TopBack()

    O(n)

    O(1)

    PopBack()

    O(n)

    Find(key)

    O(n)

    Erase(key)

    O(n)

    Empty()

    O(1)

    AddBefore(Node,Key)

    O(n)

    AddAfter(Node,Key)

    O(1)

    很显然,每当我们的操作是从后往前进行时,复杂度就会很高。因为我们需要从头开始遍历.例如PopBack,我们需要从头开始遍历。像二分搜索,更是难以实现。如果有一个和next相对的previous指针,事情会简单很多。这就是双向链表的好处。

    双向链表

    双向链表概念

    功能和单向链表一样,就是每次操作时要多对prev节点操作。每次插入和删除操作时,要处理四个节点的引用,而不是两个。

    单向链表插入时,我们只需考虑改变插入节点的前一个节点的next(如果不是插入在头节点前),和插入节点的next。而双向链表插入时我们需要考虑插入节点的前一个节点的next,插入节点的prev和next,插入节点的后一个节点的prev((如果不是插入在尾节点后)。所以需要特别仔细。

    基本API的代码实现

    288eae6aca9cde9f5b7351abdace88ab.png

    时间复杂度O(n)

    Doubly-Linked Listno tailwith tail

    PushFront(key)

    O(1)

    TopFront()

    O(1)

    PopFront()

    O(1)

    PushBack(key)

    O(n)

    O(1)

    TopBack()

    O(n)

    O(1)

    PopBack()

    O(n) O(1)

    Find(key)

    O(n)

    Erase(key)

    O(n)

    Empty()

    O(1)

    AddBefore(Node,Key)

    O(n) O(1)

    AddAfter(Node,Key)

    O(1)

    很明显,有了prev节点后,我们的PopBack和AddBefore时间复杂度都降低了,因为省去了遍历的过程。当然 ,由于多了两个链节点的引用,链节点占用的空间也会变大。所以使用双向链表就是用空间换时间。

    展开全文
  • 基本定义单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个...

    基本定义

    • 单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;
    • 链表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向-NULL的指针。

    458a275b650450d9f4dec932cc9f8076.png

    链表优点

    1. 单个结点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小。
    2. 结点的删除非常方便,不需要像线性结构那样移动剩下的数据。
    3. 结点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表。

    实现思路

    1. 头节点
    2. 节点个数
    3. 添加节点
    每次添加的元素为头节点
    1. 删除节点
    当前节点的前驱节点next指向当前节点的下一个节点,当前节点没有任何对象引用。

    代码实现

    单链表类

    //单链表类
    public class SingleLinkedList {
        //1.节点的个数
        private int size;
        //2. 头节点
        private Node head;
    
    
        public class Node{
            private Object data;//内部类元素,OBJECT类型
            private Node next;
    
            public Node() {
            }
    
            public Node(Object data) {
                this.data = data;
            }
    
            @Override
            public String toString() {
                return "Node{" +
                        "data=" + data +
                        ", next=" + next +
                        '}';
            }
        }
    
        /**
         * @param object 添加的元素
         * @return
         */
        public Object addNode(Object object){
            Node newHead = new Node(object);//每次添加的元素为头节点
            if(size == 0){
                head = newHead;
            }else {
                newHead.next = head;
                head = newHead;
            }
            size++;
            return object;
        }
    
        /**
         * 判读是否为空
         * @return
         */
        public boolean isEmpty(){
            return size == 0;
        }
    
        public void display(){
            if(isEmpty()){
                System.out.println("单向链表为空");
                return;
            }
            Node node = head;
            int tempSize = size; //临时长度
            System.out.print("[");
            while (tempSize > 0){
                System.out.print(node.data);
                if(node.next != null) {
                    System.out.print(" -> ");
                }
                node = node.next;//当前节点指向下一个节点,继续循环
                tempSize--;
            }
            System.out.print("] n");
        }
    
        /**
         * 删除头节点
         * @return
         */
        public Node deleteHead(){
            Node delNode = head;
            head = head.next;
            size--;
            return delNode;
        }
    
        public boolean delete(Object object){
            if(isEmpty()) return false;
    
            Node current = head; //指定当前节点为头节点
            Node previous = head;//指定前驱节点为头节点
    
            //判断条件,如果当前节点数据不等于需要删除的数据,则继续
            while (current.data != object){
                if(current.next == null) return false;
                previous = current;
                current = current.next;
            }
            //删除节点是否为头节点
            if(current == head){
                head = head.next;
            }else {
                //当前节点的前驱节点指定当前节点的下一个节点,当前节点没有任何对象引用。
                previous.next = current.next;
            }
            size--;
            return true;
        }
    
        public Node find(Object object){
            Node current = head;
            int tempSize = size; //临时变量,用于循环
            while (tempSize > 0){
                if(current.data.equals(object)){
                    return current;
                }else {
                    current = current.next;
                    tempSize--;
                }
            }
            return null;
    
        }
    }

    测试

    public static void main(String[] args) {
            SingleLinkedList list = new SingleLinkedList();
            list.addNode("郭嘉");
            list.addNode("司马懿");
            list.addNode("荀彧");
            list.display();
    
            System.out.println("查询数据为【司马懿】的节点:" + list.find("司马懿"));
    
            System.out.println("删除头节点:" + list.deleteHead());
            list.display();
    
            list.addNode("许攸");
            list.addNode("贾诩");
            list.display();
    
            System.out.println("删除数据为郭嘉的节点:" + list.delete("郭嘉"));
            list.display();
        }

    输出结果

    [荀彧 -> 司马懿 -> 郭嘉]
    查询数据为【司马懿】的节点:Node{data=司马懿, next=Node{data=郭嘉, next=null}}
    删除头节点:Node{data=荀彧, next=Node{data=司马懿, next=Node{data=郭嘉, next=null}}}
    [司马懿 -> 郭嘉]
    [贾诩 -> 许攸 -> 司马懿 -> 郭嘉]
    删除数据为郭嘉的节点:true
    [贾诩 -> 许攸 -> 司马懿]
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,940
精华内容 7,976
关键字:

单向链表