✨博客主页: XIN-XIANG荣
✨系列专栏:【Java实现数据结构】
✨一句短话: 难在坚持,贵在坚持,成在坚持!

文章目录

• 一. 链表的概念和分类
• 二. 无头单向非循环链表实现
• • MySigleLinkedList.java
  • IndexWrongfulException.java
  • TestList.java
  • 执行结果
  • 注意事项
• 三. 无头双向非循环链表实现
• • MyLinkedList.java
  • IndexWrongfulException.java
  • TestList.java
  • 执行结果
  • 注意事项

一. 链表的概念和分类

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

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

• 单向或者双向

• 带头或者不带头

• 循环或者非循环

这里列出这8种链表结构

1. 不带头单向不循环链表
2. 不带头单向循环链表
3. 不带头双向不循环链表
4. 不带头双向循环链表
5. 带头单向不循环链表
6. 带头单向循环链表
7. 带头双向不循环链表
8. 带头双向循环链表

这里对于带头和不带头要注意区分一下 , 带头链表中链表的头节点是固定不变的且头节点的数值域是虚拟的 (无效的 , 不存放数据) , 不管数据在哪里插入和删除 , 头节点都不会变化 ; 而不带头链表 , 链表的第一个节点 (头节点) 是有效节点 , 数值域是有效的 , 如果在不带头链表中进行头插或者删除第一个节点 , 头节点会发生变化 .

本篇博客重点介绍下面两种链表 , 使用Java语言去实现 :

• 无头单向非循环链表：

结构简单，一般不会单独用来存数据 ; 实际中更多是作为其他数据结构的子结构，如 哈希桶、图的邻接表等等。

• 无头双向不循环链表 :

在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

二. 无头单向非循环链表实现

下图所示为无头单向非循环链表的结构

MySigleLinkedList.java

public class MySigleLinkedList {
    //内部类实现节点
    static class ListNode {
        public int val;//存放元素
        public ListNode next;//记录下一个节点的引用

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;//记录头节点的引用

    //打印链表里面的数据，默认从头开始打印
    public void display() {
        ListNode cur = this.head;
        //条件不能是cur.next,否则最后一个节点无法打印
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //获取单链表的长度
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //查找某个数据key是否在单链表中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;
    }

    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        if(cur == null) {
            this.head = node;
        }else {
            //找到最后一个节点
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    //在任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) throws IndexWrongfulException{
        if(index < 0 || index > size()) {
            throw new IndexWrongfulException("index位置不合法！");
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()) {
            addLast(data);
            return;
        }
        //先走index-1步，找到要插入位置的前一个位置
        ListNode cur = findIndexSubOne(index);
        ListNode node = new ListNode(data);
        //插入，修改指向
        node.next = cur.next;
        cur.next = node;
    }

    private ListNode findIndexSubOne(int index) {
        ListNode cur = this.head;
        while(index-1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
    //删除第一次出现数据key的节点
    public void remove(int key) {
        if(this.head == null) {
            return;
        }
        //判断头节点
        if(this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        //先找到key位置的上一个位置
        ListNode cur = findPrevOfKey(key);
        if(cur == null) {
            System.out.println("不存在你要删除的元素"+key);
            return;
        }
        //删除
        cur.next = cur.next.next;
    }

    private ListNode findPrevOfKey(int key) {
        ListNode cur = this.head;
        while(cur.next != null) {
            if(cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if(this.head == null) {
            return;
        }
        //从第二个节点开始判断
        ListNode cur = this.head.next;
        ListNode prev = this.head;//记录要判断节点的上一个节点
        while(cur != null) {
            if(cur.val == key) {
                //删除
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
            //最后判断头节点
            if(this.head.val == key) {
                this.head = this.head.next;
            }
        }
    }
    /*public ListNode removeElements(int val) {
        if(head == null) {
            return null;
        }
        //从第二个元素开始判断
        ListNode cur = this.head;
        while(cur.next != null) {
            if(cur.next.val == val) {
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        //最后判断头节点
        if(this.head.val == val) {
            this.head = this.head.next;
        }
        return this.head;
    }*/

    //清空单链表
    public void clear() {
        this.head = null;
    }
}

IndexWrongfulException.java

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

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

TestList.java

public class TestList {
    public static void main(String[] args) {
        MySigleLinkedList linkedList = new MySigleLinkedList();

        System.out.println("头插测试");
        linkedList.addFirst(1);
        linkedList.addFirst(2);
        linkedList.display();

        System.out.println("尾插测试");
        linkedList.addLast(3);
        linkedList.addLast(2);
        linkedList.addLast(1);
        linkedList.addLast(4);
        linkedList.display();

        System.out.println("任意位置插入");
        try {
            linkedList.addIndex(2,666);
            linkedList.addIndex(8,666);
        } catch(IndexWrongfulException e) {
            e.printStackTrace();
        }
        linkedList.display();

        System.out.println("单链表中有"+linkedList.size()+"个数据");

        System.out.println("看单链表中是否包含某个数据");
        System.out.println(linkedList.contains(666));

        System.out.println("删除第一个指定数据");
        linkedList.remove(1);
        linkedList.remove(9);
        linkedList.display();

        System.out.println("删除全部的指定数据");
        linkedList.removeAllKey(2);
        linkedList.display();

        System.out.println("清空单链表后再添加一个数据");
        linkedList.clear();
        linkedList.addFirst(888);
        linkedList.display();
    }
}

执行结果

注意事项

1. 在代码中需要进行遍历链表时 , 要注意区分 cur != null 和 cur.next != null 的使用 , 虽然二者都可以去遍历链表 , 但cur != null , 最后一次循环判断使cur指向为null ; 而cur.next != null 的最后一次循环判断使cur指向的是链表的最后一个节点 .
2. 单链表中插入和删除数据 , 需要先找到要处理位置的上一个位置 , 然后再进行指针指向的修改 .
3. Java当中没有指针的概念 , 这里的节点通过类来实现 , 创建一个引用类型变量 , 这个引用就是Java当中的 “指针” 了 .
4. 单链表中实现清空单链表只需要置空头节点即可 , 要与双链表中的清空区分

三. 无头双向非循环链表实现

给出结构图

MyLinkedList.java

public class MyLinkedList {
    //内部类定义节点
    static class ListNode {
        public int val;
        public ListNode next;//记录下一个节点
        public ListNode prev;//记录前一个节点

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

    public ListNode head;//指向头节点
    public ListNode tail;//指向尾巴节点

    //打印链表
    public void display() {
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //获取链表中元素的个数
    public int size() {
        ListNode cur = this.head;
        int count = 0;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //判断数据在链表中是否存在
    public boolean contains(int key) {
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(this.head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
    }

    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(this.head == null) {
            this.head = node;
            this.tail = node;
            return;
        }
        this.tail.next = node;
        node.prev = this.tail;
        this.tail = node;
    }

    //在任意位置插入, 认为头节点为0位置
    public void addIndex(int index, int data) {
        if(index < 0 || index > this.size()) {
            throw new IndexWrongfulException("index位置不合法");
        }
        if(index == 0) {
            this.addFirst(data);
            return;
        }
        if(index == size()) {
            this.addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = findIndexListNode(index);
        node.next = cur;
        node.prev = cur.prev;
        cur.prev.next = node;
        cur.prev = node;
    }

    public ListNode findIndexListNode(int index) {
        ListNode cur = this.head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //删除第一个出现的指定元素
    public void remove(int key) {
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                //如果要删除的是头节点
                if(this.head == cur) {
                    this.head = this.head.next;
                    //如果链表中只有一个节点
                    if(this.head != null){
                        this.head.prev = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {//如果要删除的是尾巴节点
                        this.tail = cur.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }

    //删除全部的指定元素
    public void removeAll(int key) {
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.val == key) {
                //如果要删除的是头节点
                if(this.head == cur) {
                    this.head = this.head.next;
                    //如果链表中只有一个节点
                    if(this.head != null){
                        this.head.prev = null;
                    }
                }else{
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {//如果要删除的是尾巴节点
                        this.tail = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

    //清空
    public void clear() {
        ListNode cur =this.head;
        while(cur != null) {
            cur.prev = null;
            cur.next = null;
            cur = cur.next;
        }
        this.head = null;
        this.tail = null;
    }
}

IndexWrongfulException.java

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

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

TestList.java

public class TestList {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        System.out.println("头插测试");
        list.addFirst(1);
        list.addFirst(2);
        list.addFirst(3);
        list.display();

        System.out.println("尾插测试");
        list.addLast(4);
        list.addLast(5);
        list.addLast(6);
        list.display();

        System.out.println("获取链表中元素的个数");
        System.out.println(list.size());

        System.out.println("判断数据在链表中是否存在");
        System.out.println(list.contains(4));
        System.out.println(list.contains(8));

        System.out.println("在任意位置插入");
        list.addIndex(0, 666);
        list.addIndex(3, 666);
        list.addIndex(list.size(), 666);
        list.display();

        System.out.println("删除第一个出现的指定元素");
        list.remove(4);
        list.display();

        System.out.println("删除全部的指定元素");
        list.removeAll(666);
        list.display();

        System.out.println("清空链表后再添加一个元素");
        list.clear();
        list.addFirst(888);
        list.display();
    }
}

执行结果

注意事项

1. 与单链表中的插入和删除实现进行区分 , 这里双链表中的插入和删除 , 因为此时链表是双向的 , 所以不需要像单链表一样找要处理位置的前一个位置 , 只需要找到要处理的位置去改变前驱和后记指针指向即可 .
2. 在进行删除元素操作时 , 需要考虑的细节比较多 , 特别需要注意删除头节点与尾节点时的操作(考虑prev为null和next为null , 与删除中间节点不同) , 具体实现看上面给出的代码 .
3. 注意双链表的清空链表实现 , 与单链表中的进行区分 , 双链表中需要手动去将每个节点的两个指针域置为null , 最后再将head和tail去置空 .