文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java数据结构之链表实现(单向、双向链表及链表反转)

2024-04-02 19:55

关注

前言

之前学习的顺序表查询非常快,时间复杂度为O(1),但是增删改效率非常低,因为每一次增删改都会元素的移动。可以使用另一种存储方式-链式存储结构。

链表是一种物理存储单元上非连续、非顺序的存储结构。链表由一序列的结点(链表中的每一个元素成为结点)组成。

结点API设计

类名 Node
构造方法 Node(T t,Node next) 创建Node对象
成员变量

T item:存储数据

Node next :指向下一个结点

结点类


public class Node<T>{
    Node next;
    private T item;
 
    public Node(Node next, T item) {
        this.next = next;
        this.item = item;
    }
}

生成链表


public class TestNode {
    public static void main(String[] args) {
        // 生成结点
        Node<Integer> one = new Node<Integer>(null,12);
        Node<Integer> two = new Node<Integer>(null,16);
        Node<Integer> three = new Node<Integer>(null,11);
        Node<Integer> four = new Node<Integer>(null,10);
        //生成链表
        one.next = two;
        two.next = three;
        three.next =four;
    }
}

1、单链表

单向链表是链表的一种,它有多个结点组成每个结点都由一个数据域一个指针组成,数据域用来存储数据指针域用来指向其后结点

链表的头结点数据域不存储数据,指针域指向第一个真正存储数据的结点。

单向链表API设计

类名 LinkList
构造方法 LinkList() :创建LinkList对象
成员变量

private Node head;记录首结点

private int N; 记录链表的长度

成员内部类 private class Node;结点类
成员方法
public void clear() 清空链表
public boolean isEmpty() 判断链表是否为空,是返回true
public int length() 获取链表中的元素个数
public T get(int i) 读取并返回链表中的第i个元素的值

public void insert(T t)

往链表中插入一个元素
public void insert(T t,int i) 在链表的第i位置插入一个值为t的数据元素
public T remove(int i) 删除并返回删除链表中的第i个数据元素
public int indexof(T t) 返回链表中首次出现的指定的数据元素的序号,如不存在,则返回-1

单向链表Java代码实现


package com.ycy.Algorithm.LinkList;
 
 
import java.util.Iterator;
 

public class LinkList<T> implements Iterable<T>{
 
    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;
    }
    
    public T get(int i){
        //非法性检查
        if(i<0 || i > this.N){
            throw new RuntimeException("位置不合法");
        }
        // n也是指向头结点
        Node n = head;
        for(int index=0; index<i; index++){
            n = n.next;
        }
        return n.item;
    }
    
    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 ++;
    }
 
    
    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++;
    }
    
    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的

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

测试代码:


public class test {
    public static void main(String[] args) {
        LinkList<Integer>linkList = new LinkList<>();
        linkList.insert(1);
        linkList.insert(2);
        linkList.insert(4);
        linkList.insert(3);
        linkList.insert(1,2);
        for (Integer i : linkList) {
            System.out.print(i+" ");
        }
    }
}

运行结果:

D:\Java\jdk-12.0.2\bin\java.exe "-javaagent:D:\IDEA\IntelliJ IDEA 2019.1\lib\idea_rt.jar=3542:D:\IDEA\IntelliJ IDEA 2019.1
1 2 1 4 3 

学习完链表还是需要加以练习的,可以在LeetCode上刷题加深理解。

2、双向链表

头插法:新增节点总是插在头部

便于理解可以画图表示

头插法:原图,node是待插入的结点.

插入后图:

关键性代码:

尾插法:新增节点总是插在尾部

原图如下: 

 

插入结点后图如下:

关键性代码:

中间任意位置插入

插入之前的原图: 

 

插入到链表中间位置:

关键性代码:

代码演示:


class MyLinkedList {
    Node head;//定义双向链表的头节点
    Node last;//定义双向链表的尾节点
 
    //打印双向链表
    public void disPlay() {
        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
 
    //求双向链表的长度(之后addIndex代码会用到)
    public int size() {
        int count = 0;
        Node cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
 
    //头插法
    public void addFirst(int data) {
        Node node = new Node(data);//定义一个用作插入的节点
        //1.假设双向链表为空
        if (this.head == null) {
            this.head = node;
            this.last = node;
        } else {
            //2.双向链表不为空的情况下
            //不懂请看上面的图解,就很简单了
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        }
    }
 
    //尾插法(与头插法类似)
    public void addLast(int data) {
        //定义一个用作插入的节点
        Node node = new Node(data);
        //1.假设双向链表为空
        if (this.head == null) {
            this.head = node;
            this.last = node;
        } else {
            //2.双向链表不为空的情况下
            //不懂请看上面的图解,就很简单了
            last.next = node;
            node.prev = last;
            last = node;
        }
    }
 
    //在任意位置插入
    public void addIndex(int index, int data) {//形参index为插入元素位置,data为插入的数值
        //定义一个用作插入的节点
        Node node = new Node(data);
        Node cur = this.head;//定义一个cur用作遍历双向链表
        //1、判断插入位置的合法性
        if (index < 0 || index > size()) {
            System.out.println("插入位置不合法!!!");
            return;
        }
        //2、假设插入位置为头结点的情况下,即就是头插法
        if (index == 0) {
            addFirst(data);//调用头插法代码
            return;
        }
        //3、假设插入位置为尾结点的情况下,即就是尾插法
        if (index == size()) {
            addLast(data);//调用尾插法代码
            return;
        }
        //4、在中间任意位置的情况下
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        //不懂请看上面的图解,就很简单了
        //核心代码
        node.next = cur;
        node.prev = cur.prev;
        cur.prev = node;
        node.prev.next = node;
    }
}
 
//双向链表的节点结构
class Node {
    int val;
    Node prev;
    Node next;
 
    Node(int val) {
        this.val = val;
    }
}

3、链表反转


public void reverse(){
        if(N==0){
        //当前是空链表,不需要反转
            return;
        }
        reverse(head.next);
}
    
public Node reverse(Node curr){
        //已经到了最后一个元素
        if(curr.next==null){
        //反转后,头结点应该指向原链表中的最后一个元素
          head.next=curr;
          return curr;
        }
       //当前结点的上一个结点
       Node pre=reverse(curr.next);
       pre.next=curr;
       //当前结点的下一个结点设为null
       curr.next=null;
       //返回当前结点
       return curr;
}

总结

到此这篇关于Java数据结构之链表实现的文章就介绍到这了,更多相关Java数据结构链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯