数据结构——链表(java)

柔光的暖阳◎ 2024-03-30 13:42 2阅读 0赞

#### 文章目录 ####

*  链表
 *   *  1. 基本介绍
     *   *  1.1 定义
         *  1.2 链表分类
         *  3.不带头非循环单链表CURD
         *  4.不带头非循环双向链表CURD

## 链表 ##

### 1. 基本介绍 ###

#### 1.1 定义 ####

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

如图所示：  
![在这里插入图片描述][abb449de377046bea2ef82d3186487cd.png]

#### 1.2 链表分类 ####

单向、双向；带头、不带头；循环、非循环  
重点：单向不带头非循环、双向不带头非循环（集合类底层）

如图：单项带头非循环链表结构  
![在这里插入图片描述][de98a94971124b338c7556fa21022935.png]  
如图：单向带头循环链表结构  
![在这里插入图片描述][25e15d5593ca4aeb8842457dc34d6af7.png]  
如图：双向不带头循环链表结构  
![在这里插入图片描述][5977aac8788147e09a21725027508b5f.png]

#### 3.不带头非循环单链表CURD ####

代码展示：

package demo3;
    
    /**
     * @author zq
     * 不带头非循环单链表相关操作
     */
    public class MySingleList {
    
        class Node {
            public int val;//存储数据
            public Node next;//存储下一个节点地址
    
            public Node(int val) {
                //不知道下一个节点位置，只需要val
                this.val = val;
            }
    
        }
        public Node head;//代表当前头节点的引用
    
        //遍历链表
            //创建链表
            public void createLink(){
                Node node1 = new Node(12);
                Node node2 = new Node(45);
                Node node3 = new Node(23);
                Node node4 = new Node(90);
    
                node1.next = node2;
                node2.next = node3;
                node3.next = node4;
                head = node1;
            }
            //遍历链表,利用head遍历链表
            public void display() {
                while (head != null){
                    System.out.println(head.val);
                    head = head.next;
                }
            }
            //查找是否包含关键字key是否在单链表当中
            public boolean contains(int key){
                Node cur = head;
                while (cur != null){
                    if (cur.val == key){
                        return true;
                    }
                    cur = cur.next;
                }
                return false;
            }
            //头插法
            public void addFirst(int data){
                Node node = new Node(data);
                node.next = head;
                head = node;
            }
    
            //尾插法,需判断head是否为空
            public void addLast(int data){
                Node node = new Node(data);
                if (head == null) {
                    head = node;
                    return;
                }
                    Node cur = head;
                    while (cur.next != null) {
                        cur = cur.next;
                    }
                    cur.next = node;
                }
    
    
    
    
            //任意位置插入,第一个数据节点为0号下标
            public void addIndex(int index,int data){
                checkindex(index);
                if (index == 0){
                    addFirst(data);
                    return;
                }
                if (index == size()){
                    addLast(data);
                    return;
                }
    
                Node cur = findIndexSubOne(index);
                Node node = new Node(data);
                node.next = cur.next;
                cur.next = node;
    
    
    
            }
            /*
            找到index-1处的节点
             */
            private Node findIndexSubOne(int index){
                Node cur = head;
                int count = 0;
                while (count != index -1 ){
                    cur = cur.next;
                    count++;
                }
                return cur;
    
            }
            private void checkindex(int index){
                if (index<0||index>size()){
                    throw new IndexOutOfException("index位置不合法");
                }
            }
    
            //删除第一次出现关键字为key的节点
            public void remove(int key){
                if (head.val == key){
                    head = head.next;
                    return;
                }
              Node cur = searchPrev(key);
                if (cur == null){
                    return;
                }
              cur.next = cur.next.next;
            }
    
            //删除所有值为key的节点
            public void removeAllKey(int key){
    
                if (head == null){
                    return;
                }
                //如果前俩个节点值均为key时。
                // 或者用if放到最后，直接删掉漏掉的节点
                while (head.val==key){
                    head = head.next;
                }
                Node prev = head;
                Node cur = head.next;
                while (cur != null){
                    if (cur.val == key){
                        prev.next = cur.next;
                        cur = cur.next;
                    }else{
                        prev = cur;
                        cur = cur.next;
                    }
                }
    
            }
            //找到关键字key的前一个节点
        private Node searchPrev(int key){
                if (head== null){
                    return null;//链表为空时
                }
                Node cur = head;
                while (cur.next!= null){
                    if (cur.next.val == key){
                        return cur;
                    }
                    cur = cur.next;
                }
                return null;//没有需要删除的节点
        }
    
            //得到单链表的长度
            public int size(){
                int count = 0;
                Node cur = head;
                while (cur != null){
                    count++;
                    cur = cur.next;
                }
                return count;
            }
    
            /*
            保证列表中每一个节点都被回收
             */
            public void clear() {
                ListNode cur = head;
            while(cur != null){
                ListNode curNext = cur.next;
                cur.prev = null;
                cur.next = null;
                cur = curNext;
            }
            head = null;
            last = null;
            }
    }

#### 4.不带头非循环双向链表CURD ####

代码展示：

package demo4;
    
    import demo3.MySingleList;
    
    import java.util.List;
    
    /**
     * @author zq
     * LinkedList的实现
     * 双向链表
     */
    public class MyLinkedList {
        static class ListNode{
            ListNode prev;
            ListNode next;
            int val;
    
            public ListNode(int val) {
                //不知道下一个节点位置，只需要val
                this.val = val;
            }
    
        }
        public MyLinkedList.ListNode head;//代表当前头节点的引用
        public MyLinkedList.ListNode last;//代表最后节点的引用
    
    
        //头插法
        public void addFirst(int data){
            ListNode node = new ListNode(data);
            if (head == null) {
                head = node;
                last = node;
            }else{
                node.next = head;
                node.prev = null;
                head.prev = node;
                head = node;
            }
    
        }
        //尾插法
        public void addLast(int data){
            ListNode node = new ListNode(data);
            if (head == null){
                head = node;
                last = node;
            }else{
                last.next = node;
                node.prev = last;
                node.next = null;
                last = node;
            }
    
        }
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
            ListNode node = new ListNode(data);
            checkindex(index);
            if (index==0){
                addFirst(data);
                return;
            }
            if (index==size()){
                addLast(data);
                return;
            }
            ListNode cur = findIndex(index);
            node.next = cur;
            cur.prev.next = node;
            node.prev = cur.prev;
            cur.prev = node;
    
    
    
        }
        //判断插入位置是否合法
        private void checkindex(int index){
            if (index<0||index>size()){
                throw new IndexOutOfException("index位置不合法");
            }
        }
        /*
        找到index处的节点
             */
        private ListNode findIndex(int index){
            ListNode cur = head;
            while (index != 0){
                cur = cur.next;
                index--;
            }
            return cur;
    
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
            ListNode cur = head;
            while(cur != null){
                if (cur.val == key){
                    return true;
                }
                cur = cur.next;
            }
    
            return false;
        }
        //删除第一次出现关键字为key的节点
        public void remove(int key){
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    //删除的是头节点
                    if(cur == head) {
                        head=head.next;
                        //如果只有一个节点时处理方式
                        //否则会有空指针异常
                        if (head !=null) {
                            head.prev = null;
                        }
                    }else{
                        //中间，尾巴都能用此行代码。
                        cur.prev.next = cur.next;
                        if (cur.next != null){
                            //不是尾巴节点
                            cur.next.prev = cur.prev;
                        }else {
                            last = cur.prev;
                        }
                    }
                    return;
                }
                cur = cur.next;
            }
        }
        //删除所有值为key的节点
        public void removeAllKey(int key){
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    //删除的是头节点
                    if(cur == head) {
                        head=head.next;
                        //如果只有一个节点时处理方式
                        //否则会有空指针异常
                        if (head !=null) {
                            head.prev = null;
                        }
                    }else{
                        //中间，尾巴都能用此行代码。
                        cur.prev.next = cur.next;
                        if (cur.next != null){
                            //不是尾巴节点
                            cur.next.prev = cur.prev;
                        }else {
                            last = cur.prev;
                        }
                    }
                }
                cur = cur.next;
            }
    
    
        }
        //得到单链表的长度
        public int size(){
            int len = 0;
            ListNode cur = head;
            while (cur != null){
                cur = cur.next;
                len++;
            }
    
            return len;
        }
        public void display(){
            ListNode cur = head;
           while (cur !=null){
               System.out.print(cur.val + " ");
               cur = cur.next;
           }
        }
        public void clear(){
            head = null;
        }
    }

[abb449de377046bea2ef82d3186487cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/848b9b43d06f4671837109db0320f0c1.png
[de98a94971124b338c7556fa21022935.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/dd681f28b14d482bae0b57fa43701c9d.png
[25e15d5593ca4aeb8842457dc34d6af7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/89ead2bd9b804164b5ba37fce1544e4e.png
[5977aac8788147e09a21725027508b5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/24c537f3eda6453aa50acdbf59662cbd.png