Java数据结构之单链表与OJ题

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于数据结构的相关内容,包括了单链表与OJ题,下面一起来看一下,希望对大家有帮助。

Java数据结构之单链表与OJ题

1、什么是链表?

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

通俗点,就是每个元素是一个节点,然后用一个指针域给后面的节点连起来,第一个节点没有前驱,最后一个节点没有后继。

Java数据结构之单链表与OJ题

实际中要实现的链表的结构非常多样,以下情况组合起来就有8种链表结构:

1. 单向、双向 2. 带头、不带头 3. 循环、非循环

我们重点讲解单向非循环链表和双向非循环链表,同时这两个也是笔试中考的比较多的。

2、实现一个单向非循环链表

2.1 实现前的约定

因为链表的每个元素是一个节点,所以我们采取内部类的方式,而我们还需要定义一个头节点的引用,来始终指向头节点。

public class MySingleList {
    private ListNode head; //引用头节点
    // 链表每个元素是一个节点
    private class ListNode {
        private int val; //存放数据元素
        private ListNode next; //存放下一个节点地址
        //构造方法
        public ListNode(int val) {
            this.val = val;
        }
    }
}
登录后复制

注意:链表最少有两个域,分别是数据域和指针域,当然你也可以有多个数据域和指针域。

我们还需要实现以下几个常用的方法:

public void addFirst(int data); //头插法public void addLast(int data); //尾插法public boolean addIndex(int index,int data); //任意位置插入,第一个数据节点为0号下标public boolean contains(int key); //查找关键字key是否在单链表当中public void remove(int key); //删除第一次出现关键字为key的节点public void removeAllKey(int key); //删除所有值为key的节点public int size(); //得到单链表的长度public void clear(); //清空链表
登录后复制

2.2 addFirst 方法

public void addFirst(int data) {
    ListNode newNode = new ListNode(data); //把传过来的值放到新的节点中
    newNode.next = this.head; //新节点的next指向头节点
    this.head = newNode; //使新节点成为头节点
}
登录后复制

因为head默认是指向空的,当链表为null,也不影响这个代码的执行,不信你下来画画图咯。

2.3 addList 方法

public void addLast(int data) {
    ListNode newNode = new ListNode(data);
    // 如果链表为空的情况
    if (this.head == null) {
        this.head = newNode;
        return;
    }
    // 先找到最后一个节点
    ListNode cur = this.head;
    while (cur.next != null) {
        cur = cur.next;
    }
    cur.next = newNode;
}
登录后复制

2.4 addIndex 方法

//任意位置插入,第一个数据节点为0号下标
private ListNode findIndexPrevNode(int index) {
    ListNode cur = this.head;
    while (index - 1 != 0) {
        cur = cur.next;
        index--;
    }
    return cur;
}
public boolean addIndex(int index,int data) {
    // 判断index下标的有效性
    if (index < 0 || index > size()) {
        return false;
    }
    // 如果在0下标插入则是头插
    if (index == 0) {
        addFirst(data); //头插
        return true;
    }
    // 如果在末尾插入则是尾插
    if (index == size()) {
        addLast(data); //尾插
        return true;
    }    ListNode newNode = new ListNode(data); //新节点
    // 在中间插入
    ListNode prevNode = findIndexPrevNode(index); //找到index下标的前一个节点
    newNode.next = prevNode.next; //新节点的next被改为index的位置的节点
    prevNode.next = newNode; //index位置前一个节点next被改成新节点
    return true;
}
登录后复制

郑重声明:本文版权包含图片归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们(delete@yzlfxy.com)修改或删除,多谢。

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。

留言与评论(共有 0 条评论)
昵称:
匿名发表
   
验证码: