【DS】链表的介绍和实现(单/双链表)

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

文章目录

一. 链表的概念和分类

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

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

• 单向或者双向

• 带头或者不带头

• 循环或者非循环

这里列出这8种链表结构

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

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

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

• 无头单向非循环链表：

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

• 无头双向不循环链表 :

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

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

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

MySigleLinkedList.java

publicclassMySigleLinkedList{//内部类实现节点staticclassListNode{publicint val;//存放元素publicListNode next;//记录下一个节点的引用publicListNode(int val){this.val = val;}}publicListNode head;//记录头节点的引用//打印链表里面的数据，默认从头开始打印publicvoiddisplay(){ListNode cur =this.head;//条件不能是cur.next,否则最后一个节点无法打印while(cur !=null){System.out.print(cur.val+" ");
            cur = cur.next;}System.out.println();}//获取单链表的长度publicintsize(){int count =0;ListNode cur =this.head;while(cur !=null){
            count++;
            cur = cur.next;}return count;}//查找某个数据key是否在单链表中publicbooleancontains(int key){ListNode cur =this.head;while(cur !=null){if(cur.val == key){returntrue;}
            cur = cur.next;}returnfalse;}//头插法publicvoidaddFirst(int data){ListNode node =newListNode(data);
        node.next =this.head;this.head = node;}//尾插法publicvoidaddLast(int data){ListNode node =newListNode(data);ListNode cur =this.head;if(cur ==null){this.head = node;}else{//找到最后一个节点while(cur.next !=null){
                cur = cur.next;}
            cur.next = node;}}//在任意位置插入,第一个数据节点为0号下标publicvoidaddIndex(int index,int data)throwsIndexWrongfulException{if(index <0|| index >size()){thrownewIndexWrongfulException("index位置不合法！");}if(index ==0){addFirst(data);return;}if(index ==size()){addLast(data);return;}//先走index-1步，找到要插入位置的前一个位置ListNode cur =findIndexSubOne(index);ListNode node =newListNode(data);//插入，修改指向
        node.next = cur.next;
        cur.next = node;}privateListNodefindIndexSubOne(int index){ListNode cur =this.head;while(index-1!=0){
            cur = cur.next;
            index--;}return cur;}//删除第一次出现数据key的节点publicvoidremove(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;}privateListNodefindPrevOfKey(int key){ListNode cur =this.head;while(cur.next !=null){if(cur.next.val == key){return cur;}
            cur = cur.next;}returnnull;}//删除所有值为key的节点publicvoidremoveAllKey(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;
    }*///清空单链表publicvoidclear(){this.head =null;}}

IndexWrongfulException.java

publicclassIndexWrongfulExceptionextendsRuntimeException{publicIndexWrongfulException(){}publicIndexWrongfulException(String message){super(message);}}

TestList.java

publicclassTestList{publicstaticvoidmain(String[] args){MySigleLinkedList linkedList =newMySigleLinkedList();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

publicclassMyLinkedList{//内部类定义节点staticclassListNode{publicint val;publicListNode next;//记录下一个节点publicListNode prev;//记录前一个节点publicListNode(int val){this.val = val;}}publicListNode head;//指向头节点publicListNode tail;//指向尾巴节点//打印链表publicvoiddisplay(){ListNode cur =this.head;while(cur !=null){System.out.print(cur.val+" ");
            cur = cur.next;}System.out.println();}//获取链表中元素的个数publicintsize(){ListNode cur =this.head;int count =0;while(cur !=null){
            count++;
            cur = cur.next;}return count;}//判断数据在链表中是否存在publicbooleancontains(int key){ListNode cur =this.head;while(cur !=null){if(cur.val == key){returntrue;}
            cur = cur.next;}returnfalse;}//头插法publicvoidaddFirst(int data){ListNode node =newListNode(data);if(this.head ==null){this.head = node;this.tail = node;return;}
        node.next =this.head;this.head.prev = node;this.head = node;}//尾插法publicvoidaddLast(int data){ListNode node =newListNode(data);if(this.head ==null){this.head = node;this.tail = node;return;}this.tail.next = node;
        node.prev =this.tail;this.tail = node;}//在任意位置插入, 认为头节点为0位置publicvoidaddIndex(int index,int data){if(index <0|| index >this.size()){thrownewIndexWrongfulException("index位置不合法");}if(index ==0){this.addFirst(data);return;}if(index ==size()){this.addLast(data);return;}ListNode node =newListNode(data);ListNode cur =findIndexListNode(index);
        node.next = cur;
        node.prev = cur.prev;
        cur.prev.next = node;
        cur.prev = node;}publicListNodefindIndexListNode(int index){ListNode cur =this.head;while(index !=0){
            cur = cur.next;
            index--;}return cur;}//删除第一个出现的指定元素publicvoidremove(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;}}//删除全部的指定元素publicvoidremoveAll(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;}}//清空publicvoidclear(){ListNode cur =this.head;while(cur !=null){
            cur.prev =null;
            cur.next =null;
            cur = cur.next;}this.head =null;this.tail =null;}}

IndexWrongfulException.java

publicclassIndexWrongfulExceptionextendsRuntimeException{publicIndexWrongfulException(){}publicIndexWrongfulException(String message){super(message);}}

TestList.java

publicclassTestList{publicstaticvoidmain(String[] args){MyLinkedList list =newMyLinkedList();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去置空 .