单链表的定义及其模拟实现——java

系统管理员 2024-03-22 15:44 77阅读 0赞

## 链表 ##

### 1. 链表的概念及结构 ###

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。  
![在这里插入图片描述][5addde82b7f84a199420a5978375a763.png]实际中链表的结构非常多样，以下情况组合起来就有8种链表结构  
1.单向或者双向  
![在这里插入图片描述][22860b7d4928428daadd07e3e1661a53.png]  
2. 带头或者不带头  
![在这里插入图片描述][a991bd1940fe4710b2e800b7f18b8d91.png]3. 循环或者非循环  
![在这里插入图片描述][82e7c14777254500b2b86ba1b39e67e4.png]虽然有这么多的链表的结构，但是我们重点掌握两种:  
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多  
![在这里插入图片描述][1549d75748d74d37b6edee2be1e35327.png]

### 2.自己实现单向的无头链表 ###

#### 2.1无头结点的单向链表定义 ####

public class MySingleList {
        
    
        //代表当前列表的头结点的引用
        public Node head;
    
        //定义一个Node内部类
        class Node{
        
            public int val;
            public Node next;
            //构造方法，注意,结点的构造方法中是不构造next的，因为初始并不知道单个结点指向那里
            public Node(int val) {
        
                 this.val = val;
            }
        }
    }

#### 2.2无头结点的单向链表部分方法实现 ####

package demo1;
    
    
    public class MySingleList {
        
        //代表当前列表的头结点的引用
        public Node head;
    
        //定义一个Node内部类
        class Node {
        
            public int val;
            public Node next;
    
            //构造方法
            public Node(int val) {
        
                this.val = val;
                this.next = null;
            }
        }
    
        //头插法 O(1)
        public void addFirst(int data) {
        
            Node node = new Node(data);
            node.next = this.head;
            this.head = node;
        }
    
        //尾插法 O(N)
        public void addLast(int data) {
        
            Node node = new Node(data);
            Node cur = this.head;
            if (cur == null) {
        
                this.head = node;
            } else {
        
                while (cur.next != null) {
        
                    cur = cur.next;
                }
                cur.next = node;
            }
        }
    
    
        //MySingleList的方法
    
        //任意位置插入
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index, int data) {
        
            indexIsValid(index);
            Node node = new Node(data);
            //找到index的前一个结点
            if (index == 0) {
        
                node.next = head;
                head = node;
            } else {
        
                Node pre = findPreIndex(index);
                node.next = pre.next;
                pre.next = node;
            }
        }
    
        //找indexd的前驱结点
        private Node findPreIndex(int index) {
        
            Node pre = this.head;
            for (int i = 0; i < index - 1; i++) {
        
                pre = pre.next;
            }
            return pre;
        }
    
        //判断插入的index是否合法
        private boolean indexIsValid(int index) {
        
            if (index < 0 || index > this.size()) {
        
                throw new ListIndexOutOfException("index的值不合法！");
            }
            return true;
        }
    
        //遍历打印
        public void display() {
        
            Node cur = this.head;
            while (cur != null) {
        
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    
        //查找关键字key是不是在单链表里
        public boolean contains(int key) {
        
            Node cur = this.head;
            while (cur != null) {
        
                if (cur.val == key) {
        
                    return true;
                } else {
        
                    cur = cur.next;
                }
            }
            return false;
        }
    
        //删除第一次出现关键字为key的节点
        public void remove(int key) {
        
            if (head.val == key) {
        
                Node cur = head;
                head = head.next;
                cur = null;
            } else {
        
                Node cur = head.next;
                while (cur != null) {
        
                    if (cur.val == key) {
        
                        Node pre = findPreKey(key);
                        pre.next = cur.next;
                        cur = null;
                    } else {
        
                        cur = cur.next;
                    }
                }
            }
        }
    
        //删除所有k的结点
        public void removeAllKey(int key){
        
            //这种方法的时间复杂度是O(n^2),复杂度太高
           /* Node cur = head;
            while(cur != null){
                remove(key);
                cur = cur.next;
            }*/
    
            if(head == null){
        
                return;
            }
            Node pre = head;
            Node cur = head.next;
            while(cur != null){
        
                if(cur.val == key){
        
                    cur= cur.next;
                    pre.next = cur;
                }else{
        
                    cur = cur.next;
                    pre = pre.next;
                }
                //但是一开始的头结点还没处理
                if(head.val == key){
        
                    head = head.next;
                }
                //注意这个对头结点的判断一定是放在最后的吧，不然就是不对的，如果放在开头那么新的头结点还是不能判断
            }
        }
    
        private Node findPreKey(int key) {
        
            if (head == null) {
        
                return null;
            }
            Node pre = head;
            Node cur = head.next;
            while (cur != null) {
        
                if (cur.val != key) {
        
                    cur = cur.next;
                    pre = pre.next;
                } else {
        
                    return pre;
                }
            }
            return null;
        }
    
    
        //计算单链表长度 0(N)
        public int size() {
        
            Node cur = this.head;
            int count = 0;
            while (cur != null) {
        
                count++;
                cur = cur.next;
            }
            return count;
        }
    }

`ListIndexOutOfException`的定义

package demo1;
    
    public class ListIndexOutOfException extends RuntimeException{
        
        public ListIndexOutOfException() {
        
        }
    
        public ListIndexOutOfException(String message) {
        
            super(message);
        }
    }

测试代码（主函数）

package demo1;
    
    public class Test {
        
        public static void main(String[] args) {
        
            MySingleList mySingleList = new MySingleList();
    
            System.out.println("addFirst验证");
            mySingleList.addFirst(15);
            mySingleList.addFirst(14);
            mySingleList.addFirst(13);
            mySingleList.addFirst(12);
            mySingleList.display();
            System.out.println();
    
            System.out.println("addLast验证");
            MySingleList mySingleList1 = new MySingleList();
            mySingleList1.addLast(12);
            mySingleList1.addLast(13);
            mySingleList1.addLast(14);
            mySingleList1.addLast(15);
            mySingleList1.display();
            System.out.println();
    
            System.out.println("addIndex验证");
            mySingleList.addIndex(0, 11);
            mySingleList.display();
            mySingleList.addIndex(5, 16);
            mySingleList.display();
            System.out.println();
    
            System.out.println("index不合法测试");
            try{
        
                mySingleList.addIndex(-1, 10);
                mySingleList.addIndex(7, 10);
            }catch (ListIndexOutOfException e){
        
                e.printStackTrace();
            }
    
            System.out.println("remov测试");
            mySingleList.remove(11);
            mySingleList.display();
            mySingleList.remove(16);
            mySingleList.display();
            System.out.println();
    
            System.out.println("removAllkey测试");
            mySingleList.addFirst(13);
            mySingleList.display();
            mySingleList.removeAllKey(13);
            mySingleList.display();
            System.out.println();
    
            System.out.println("contains测试");
            System.out.println( mySingleList.contains(116));
            System.out.println( mySingleList.contains(13));
            System.out.println();
    
            System.out.println("size测试");
            System.out.println(mySingleList.size());
            System.out.println();
        }
    }

测试结果  
![在这里插入图片描述][3cfa84fb5ee542f8802f67ef24385503.png]

[5addde82b7f84a199420a5978375a763.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/4e62d8dc7df04d06ab209f207478dc74.png
[22860b7d4928428daadd07e3e1661a53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/5f7adede031c4c7a9b6f5b7df4624a20.png
[a991bd1940fe4710b2e800b7f18b8d91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/ad0ac0a27b444dcda9f95660d945fb77.png
[82e7c14777254500b2b86ba1b39e67e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/bc0f0524187e44d999258b58ff44213a.png
[1549d75748d74d37b6edee2be1e35327.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/da955cc8d39b459fa11e36b6f15e6ffc.png
[3cfa84fb5ee542f8802f67ef24385503.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/f5ed68418d6f410c941aa19de08e0c7d.png