数据结构之链表

简介

链表是很常见的一种数据结构,其数据呈线性排列,有许多的应用场景,例如LRU算法、Java的一些类的实现等。链表的形式有很多,常用的有单向链表、双向链表、循环链表等。

链表的结构

相对于链表,数组我们会更熟悉一些。所以拿数组和链表(单向链表)做个对比,引出链表的结构。

从图中可以看出,数组的存储,需要连续的内存空间。而链表恰恰相反,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用。上图中,我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址(如上图黑色的箭头),我们把这个记录下个结点地址的指针叫作后继指针next。所以,单链表的结构如下图所示:

上图中,其中有两个结点是比较特殊的,它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点,把最后一个结点叫作尾结点。其中,头结点用来记录链表的基地址。有了它,我们就可以遍历得到整条链表。而尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址NULL,表示这是链表上最后一个结点。需要注意的是,上图的单链表中,是有头结点的,还有一种,是没有头结点的单链表。

对应Java语言的话,我们可以这么定义一个链表:

public class ListNode { 
    int val; 
    ListNode next = null; 
    ListNode(int val) { 
       this.val = val; 
    } 
}

链表的遍历、插入和删除

我们先来看一下插入和删除的示意图:

链表的遍历

根据链表的结构,很容易能够写出链表的遍历。

public static class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public static ListNode node;

/**
 * 构造一个链表
 * @return
 */
public static void init(){
    node = new ListNode(0);
    ListNode node1 = new ListNode(1);
    ListNode node2 = new ListNode(2);
    ListNode node3 = new ListNode(3);
    ListNode node4 = new ListNode(4);
    node.next = node1;
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
}

/**
 * 非递遍历链表
 * @param head
 */
public static void print(ListNode head){
    while(head!=null){
        System.out.println(head.val);
        head=head.next;//索引向后移位
    }
}

/**
 * 递归遍历链表
 * @param head
 */
public static void printByLoop(ListNode head){
    if(head!=null){
        System.out.println(head.val);
        ListNode node=head.next;
        printByLoop(node);//递归调用
    }
}

需要注意的是,非递归遍历链表,会改变链表的头结点的位置。

链表的插入

隐藏内容,您需要满足以下条件方可查看
End

人已赞赏
DemoJava编程语言

【JavaDemo】③.控制台跑得快

2020-4-22 15:01:12

Mysql编程语言

Mysql面试题汇总

2020-5-27 9:30:26

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索