java实现的无头单向非循环链表

时间：2024-10-02 07:34:14

java实现的无头单向非循环链表

  • ArrayList的缺陷
  • 链表
    • 链表的概念及结构
    • 无头单向非循环链表的实现
    • 链表OJ题

ArrayList的缺陷

由于ArrayList底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(N)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景，因此java集合中又引入了LinkedList，即链表结构。

链表

链表的概念及结构

链表是一种物理存储结构上非连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。在这里插入图片描述
链式结构在逻辑上是连续的，但是在物理上不一定连续，现实中的结点一般是从堆上申请出来的，从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

  1. 单向或者双向
    在这里插入图片描述

  2. 带头或者不带头
    在这里插入图片描述

  3. 循环或者非循环

在这里插入图片描述
所以有八种链表结构
单向带头循环链表，双向带头循环链表
单向不带头循环链表，双向不带头循环链表
单向带头非循环链表，双向带头非循环链表
单向不带头非循环链表，双向不带头非循环链表
虽然有这么多的链表的结构，重点需要我们掌握两种：

  • 无头单向非循环链表：结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希，图的邻接表等等
  • 无头双向链表：在java的集合框架中LinkedList底层实现就是无头双向循环链表。

无头单向非循环链表的实现

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

public class MySingleList implements IList{

    //静态内部类创建节点
    static class LinkNode{
        public int value;
        public LinkNode next;

        public LinkNode(int value) {
            this.value = value;
        }
    }

    public LinkNode head;

    @Override
    public void addFirst(int data) {

    }

    @Override
    public void addLast(int data) {

    }

    @Override
    public void addIndex(int index, int data) {

    }

    @Override
    public boolean contains(int key) {
        return false;
    }

    @Override
    public void remove(int key) {

    }

    @Override
    public void removeAllKey(int key) {

    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void clear() {

    }

    @Override
    public void display() {

    }
}

我们先从打印链表开始，如果我们使用head引用来遍历打印，直到遇到null，到最后head到了null，我们就找不到头节点了，所以我们可以另外使用一个cur引用来遍历。

@Override
public void display() {
    LinkNode cur = this.head;
    while(cur != null){
        System.out.print(cur.value + " ");
        cur = cur.next;
    }
    System.out.println();
}

我们可以通过自己手动创建链表，来测试我们的打印链表方法

public void createSingleLink(){
    LinkNode node0 = new LinkNode(12);
    LinkNode node1 = new LinkNode(23);
    LinkNode node2 = new LinkNode(34);
    LinkNode node3 = new LinkNode(45);
    LinkNode node4 = new LinkNode(56);

    this.head = node0;
    node0.next = node1;
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = null;
}

public class Test {
    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.createSingleLink();
        list.display();
    }
    //结果为：12 23 34 45 56 
}

接下来实现size()求链表节点个数，依然通过一个cur来遍历并计数。

@Override
public int size() {
    int count = 0;
    LinkNode cur = this.head;
    while(cur != null){
        count++;
        cur = cur.next;
    }
    return count;
}

public class Test {
    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.createSingleLink();
        System.out.println(list.size());
    }
    //结果为：5
}

接下来实现查找是否包含关键字key是否在单链表当中的方法，我们依然通过遍历找到该key，返回true，找不到返回false

@Override
public boolean contains(int key) {
     LinkNode cur = this.head;
     while(cur != null){
         if(cur.value == key){
             return true;
         }
         cur = cur.next;
     }
     return false;
 }

public class Test {
    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.createSingleLink();
        //12 23 34 45 56
        System.out.println(list.contains(12));
        System.out.println(list.contains(34));
        System.out.println(list.contains(56));
        System.out.println(list.contains(100));
    }
    //结果为：true
    //true
    //true
    //false
}

接下来实现头插法，也就是在链表头部插入节点
在这里插入图片描述

@Override
public void addFirst(int data) {
    LinkNode newNode = new LinkNode(data);
    newNode.next = this.head;
    this.head = newNode;
}

public class Test {
    public static void main(String[] args) {
        MySingleList list1 = new MySingleList();
        list1.createSingleLink();
        list1.addFirst(99);
        list1.display();
        MySingleList list = new MySingleList();
        list.addFirst(56);
        list.addFirst(45);
        list.addFirst(34);
        list.addFirst(23);
        list.addFirst(12);
        list.addFirst(99);
        list.display();
    }
    //结果为：
    //99 12 23 34 45 56
    //99 12 23 34 45 56
}

接下来实现尾插法，我们需要先找到尾节点，再进行插入，还有我们还要考虑到如果链表为空时，代码是否能执行，是否需要我们再对其另外的实现
在这里插入图片描述
在这里插入图片描述

@Override
public void addLast(int data) {
    LinkNode newNode = new LinkNode(data);
    //如果链表为空
    if(this.head == null){
        this.head = newNode;       //直接将head指向新结点
        return;
    }
    //链表非空
    //首先找到尾结点
    LinkNode cur = this.head;
    while(cur.next != null){    //当cur走到尾结点，cur.next == null退出循环，cur指向尾结点
        cur = cur.next;
    }
    cur.next = newNode;
}

public class Test {
    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.addLast(56);
        list.addLast(99);
        list.display();
    }
    //结果为：
    //12 23 34 45 56 99
}

接下来实现任意位置插入的方法,第一个数据节点为0号下标，任意位置插入涉及尾插，头插，还有中间插入，中间插入需要修改前后指向，所以需要找到插入位置的前一个，就可以实现互相绑定，而且绑定有一个规律：所有的绑定，优先绑定后面。如果优先绑定前面，可能会出现问题，例如该方法。还有我们要考虑到任意位置，是所有位置吗，我们还需要对index进行检查，不能小于0，也不能大于size();
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
如果先绑定前面会出现什么问题呢？
在这里插入图片描述

public class IndexIllegal extends RuntimeException{
    public IndexIllegal() {
    }

    public IndexIllegal(String message) {
        super(message);
    }
}

private void checkIndex(int index) throws IndexIllegal{
    if(index < 0 || index > size()){
        throw new IndexIllegal("插入位置不合法");
    }
}

@Override
public void addIndex(int index, int data) {
    try{
        checkIndex(index);
        int len = size();   //用一个变量存储就不用一直调用方法
        if(index == 0){
            addFirst(data);
            return;
        }
        if(index == len){
            addLast(data);
            return;
        }
        LinkNode newNode = new LinkNode(data);
        LinkNode cur = this.head;
        while(index - 1 != 0){
            cur = cur.next;
            index--;
        }
        newNode.next = cur.next;
        cur.next = newNode;
    }catch(IndexIllegal e){
        e.printStackTrace();
    }

}

public class Test {
    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.addLast(56);
        list.display();
        list.addIndex(0,11);
        list.display();
        list.addIndex(6,66);
        list.display();
        list.addIndex(3,33);
        list.display();
        //list.addIndex(100,77);
    }
    //结果为：
    //12 23 34 45 56
    //11 12 23 34 45 56
    //11 12 23 34 45 56 66
    //11 12 23 33 34 45 56 66
}

接下来实现删除第一次出现关键字为key的节点的方法
在这里插入图片描述

在这里插入图片描述

@Override
public void remove(int key) {
    if(this.head == null){
        return;
    }
    if(this.head.value == key){
        this.head = this.head.next;
        return;
    }
    LinkNode cur = this.head;
    while(cur.next != null){
        if(cur.next.value == key){
            LinkNode del = cur.next;
            cur.next = del.next;    //也可以写成 cur.next = cur.next.next;
            return;
        }
        cur = cur.next;
    }
}

public class Test {
    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.addLast(56);
        list.display();
        list.remove(12);
        list.display();
        list.remove(56);
        list.display();
        list.remove(34);
        list.display();
    }
    //结果为：
    //12 23 34 45 56 
    //23 34 45 56 
    //23 34 45 
    //23 45 
}

接下来实现删除所有值为key的节点的方法
在这里插入图片描述
在这里插入图片描述

@Override
public void removeAllKey(int key) {
    //如果链表为空，不能删
    if(this.head == null){
        return;
    }
    LinkNode prev = this.head;
    LinkNode cur = this.head.next;
    while(cur != null){
        if(cur.value == key){
            prev.next = cur.next;
            cur = cur.next;
        }else{
            prev = cur;
            cur = cur.next;
        }
    }
    if(this.head.value == key){
        this.head = this.head.next;
    }
}

public class Test {
    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(23);
        list.addLast(23);
        list.addLast(34);
        list.addLast(23);
        list.addLast(56);
        list.display();
        list.removeAllKey(<

相关文章