《Java小子怒闯数据结构九重天》第五重天——链表

简介: 自古以来数据结构界就分为九重天,据说冲破这九重天之后就可以去进攻算法界最终修炼最后成佬,受万人敬仰,以下是第五重的内容。

前言


自古以来数据结构界就分为九重天,据说冲破这九重天之后就可以去进攻算法界最终修炼最后成佬,受万人敬仰。


但是这谈何容易,因为每一重天都有神兽把守,想要冲破每一重天都必须收服守护的神兽才行。


守护九重天的神兽分别是:数组、字符串、栈、队列、链表、树、散列表、堆、图。可见他们的战斗力也是逐层增强的。想只凭靠自身的能力拿下他们谈何容易。


不过大家不必惊慌,我这里有一本上古秘籍《Java小子怒闯数据结构九重天》,里面有每一重天神兽的攻略。只要修炼者仔细钻研里面的每一篇,对九重天了如指掌之后,冲破这九重天也是易如反掌的。


今天为大家带来第五重天的攻略!

image.png

1.🌀链表的基础知识

链表是一种线性表数据结构。它使用一组任意的存储单元(可以是连续的,也可以是不连续的),来存储一组具有相同类型的数据。

简单来说链表是实现线性表的链式存储结构的基础。


链表是一种通过指针串联在一起的线性结构,每一个节点是由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。


节点情况如下:


数据域 指针域

date next

上面的介绍都是单链表相关的,除了单链表我们还有双向链表,循环链表等。


双链表


双链表顾名思义就是比单链表高级了一点,一个双链表的结点在单链表的基础上又增加了一个指针,这个指针指向它的前一个结点


节点情况如下:


指针域 数据域 指针域

prior date next

循环链表


之前的链表都是条状的,循环链表是头尾相连了,就是将链表的尾部与头部连接起来。有因为条状链表有单链表与双链表之分,所以循环链表也有两种分别是:循环单链表与循环双链表


对于循环单链表我们一般设置尾指针这样操作效率会更高。


对于循环双链表我们头结点的prior结点指向最后一个节点,尾结点的next指针指向头结点,以形成循环双链表。


2.🌀Java实例化链表

想要实例化链表就得先创建一个链表的结构类,这个类代表的是每一个节点结构。


之前提到过每一个节点是由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。


所以链表节点结构定义为:


class ListNode {
    int val;       // 节点值
    ListNode next; // 后继节点引用
    ListNode(int x) { 
      val = x; 
    }
}



使用定义的这个链表结构我们可以自己构造一个链表如下:


// 实例化节点

ListNode n1 = new ListNode(4); // 节点 head
ListNode n2 = new ListNode(5);
ListNode n3 = new ListNode(1);


// 连接节点使之成为链表

n1.next = n2;
n2.next = n3;
n3.next = null;



我们构造出来的链表如下图:


image.png

3.🌀Java实现单链表

其中实现了Iterable接口,提供了遍历方式。


import java.util.Iterator;
/**
 * 链表的head是不可以动的
 * @param 
 */
public class LinkList implements Iterable{
    private Node head;//头结点,链表的head是不可以动的
    private int N;//结点个数
  //构造方法
    public LinkList() {
        this.head = new Node(null,null);
        N = 0;
    }
    //结点内部类
    private class Node{
        //存储数据
        T item;
        //下一个结点
        Node next;
        public Node(T item,Node next) {
            this.item = item;
            this.next = next;
        }
    }
    //清空链表
    public void clear(){
        head.item=null;
        head.next=null;// 头节点next为null就是空链表
        this.N=0;
    }
    //判断链表是否为空
    public boolean isEmpty(){
        return this.N==0;
    }
    //获取链表的长度
    public int length(){
        return this.N;
    }
    //读取链表第i位置的元素值并返回
    public T get(int i){
        //非法性检查
        if(i<0 || i > this.N){
            throw new RuntimeException("位置不合法");
        }
        // n也是指向头结点
        Node n = head;
        for(int index=0; index
            n = n.next;
        }
        return n.item;
    }
    //往链表中插入数据t
    public void insert(T t){
        // head不可以移动,不然就无法在找到链表
        // 定义一个临时的Node也指向head的指针就可以通过移动该指针就可以
        Node n = head;
        // 获取尾节点
        while(true){
            // 当刚好就一个节点时(头节点)
            if(n.next == null){
                break;
            }
            n = n.next;
        }
        //当为空表时,就可以插入
        Node node = new Node(t, null);
        n.next =node;
        this.N ++;
    }
    //在第i位置上插入数据t
    public void insert(T t,int i){
        // 非法性检查
        if(i < 0 || i > this.N){
            throw  new RuntimeException("插入位置非法");
        }
        Node pre = head;
        for(int index=0;index <= i-1; index++){
            pre = pre.next;
        }
        Node current = pre.next;
        //先链接后面结点
        Node newNode = new Node(t,null);
        pre.next = newNode;
        newNode.next = current;
        this.N++;
    }
    //移除并返回第i位置的元素值
    public  T remove(int i){
        // 非法性检查
        if(i < 0 || i >this.N){
            throw  new RuntimeException("删除位置有误");
        }
        Node n =head;
        for(int index=0;index <= i-1;index ++){
             n = n.next;
        }
        //要删除的节点
        Node curr = n.next;
        n.next = curr.next;
        this.N--;//结点个数减一
        return curr.item;
    }
    //查找元素t在链表中第一次出现的位置
    public int indexof(T t){
        Node n = head;
        for(int i = 0; n.next != null;i++){
            n =n.next;
            if(n.item.equals(t)){
                return i;
            }
        }
        return -1;
    }
    @Override
    public Iterator iterator() {
        return new Iterator() {
            Node n =head;
            @Override
            public boolean hasNext() {
                return n.next !=null;
            }
            @Override
            public Object next() {
                //下移一个指针
                n = n.next;
                return n.item;
            }
        };
    }
}


补充一点:链表的赋值给新的链表后,两个链表是会相会影响的,说白了就是把地址赋值给它了,他们操作是同一块内存的同一个对象。


Node n = head;


把head赋值给n,现在对n操作也是会影响head的。


4.🌀链表进阶练习

Leetcode 206. 反转链表

微信图片_20220523230415.png

题解:


我们可以申请两个指针,第一个指针叫 pre,最初是指向 null 的。

第二个指针 cur 指向 head,然后不断遍历 cur。

每次迭代到 cur,都将 cur 的 next 指向 pre,然后 pre 和 cur 前进一位。

都迭代完了(cur 变成 null 了),pre 就是最后一个节点了。


代码如下:

class Solution {
  public ListNode reverseList(ListNode head) {
  //申请节点,pre和 cur,pre指向null
  ListNode pre = null;
  ListNode cur = head;
  ListNode tmp = null;
  while(cur!=null) {
    //记录当前节点的下一个节点
    tmp = cur.next;
    //然后将当前节点指向pre
    cur.next = pre;
    //pre和cur节点都前进一位
    pre = cur;
    cur = tmp;
  }
  return pre;
  }
}


结语

恭喜你修炼到这里,你已经基本有了收服神兽链表的能力。神兽链表是我们到进攻算法界最重要的能力之一。大家不可懈怠。



相关文章
|
1月前
|
Java
【Java集合类面试二十六】、介绍一下ArrayList的数据结构?
ArrayList是基于可动态扩展的数组实现的,支持快速随机访问,但在插入和删除操作时可能需要数组复制而性能较差。
|
1月前
|
存储 设计模式 算法
JAVA中的常见数据结构
JAVA中的常见数据结构
|
15天前
|
存储 Java 索引
【数据结构】链表从实现到应用,保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同,其元素在内存中非连续分布,通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念,包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表,说明了其拥有前后两个指针的特点,并展示了相关操作的代码实现。最后,对比了ArrayList与LinkedList的不同之处,包括它们底层实现、时间复杂度以及适用场景等方面。
32 10
【数据结构】链表从实现到应用,保姆级攻略
|
29天前
|
存储 Java
|
1月前
|
存储 C语言
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
|
1月前
|
存储 Java
数据结构中的哈希表(java实现)利用哈希表实现学生信息的存储
这篇文章通过Java代码示例展示了如何实现哈希表,包括定义结点类、链表类、数组存储多条链表,并使用简单的散列函数处理冲突,以及如何利用哈希表存储和查询学生信息。
数据结构中的哈希表(java实现)利用哈希表实现学生信息的存储
|
1月前
|
存储 Java
java实现单链表的创建、增、删、改、查
这篇文章详细介绍了Java中如何实现单链表的创建以及对单链表进行增加、删除、修改、查询等操作的方法,并提供了相应的代码示例。
java实现单链表的创建、增、删、改、查
|
28天前
|
存储 Java 开发者
揭秘!HashMap底层结构大起底:从数组到链表,再到红黑树,Java性能优化的秘密武器!
【8月更文挑战第24天】HashMap是Java集合框架中的核心组件,以其高效的键值对存储和快速访问能力广受开发者欢迎。在JDK 1.8及以后版本中,HashMap采用了数组+链表+红黑树的混合结构,实现了高性能的同时解决了哈希冲突问题。数组作为基石确保了快速定位;链表则用于处理哈希冲突;而当链表长度达到一定阈值时,通过转换为红黑树进一步提升性能。此外,HashMap还具备动态扩容机制,当负载因子超过预设值时自动扩大容量并重新哈希,确保整体性能。通过对HashMap底层结构的深入了解,我们可以更好地利用其优势解决实际开发中的问题。
47 0
|
1月前
|
存储 算法 Java
"解锁Java对象数据结构的奥秘:从基础到实战,与热点技术共舞,让你的编程之路更激情四溢!"
【8月更文挑战第21天】Java以对象为核心,它是程序的基本单元与数据处理的基础。对象源自类,拥有属性(字段)和方法。对象在内存中分为对象头(含哈希码、GC信息等)和实例数据区(存储属性值)。例如,`Student`类定义了姓名、年龄等属性及相应的方法。通过`new`关键字实例化对象并调用其方法进行数据操作,是Java编程的关键技能。
27 0
|
1月前
|
存储 Java 程序员
"揭秘HashMap底层实现:从数组到链表,再到红黑树,掌握高效数据结构的秘密武器!"
【8月更文挑战第21天】HashMap是Java中重要的数据结构,采用数组+链表/红黑树实现,确保高效查询与更新。构造方法初始化数组,默认容量16,负载因子0.75触发扩容。`put`操作通过计算`hashCode`定位元素,利用链表或红黑树处理冲突。`get`和`remove`操作类似地定位并返回或移除元素。JDK 1.8优化了链表转红黑树机制,提升性能。理解这些原理能帮助我们更高效地应用HashMap。
30 0