java的LinkList模拟实现

以你之姓@ 2024-03-17 11:14 52阅读 0赞

### LinkList模拟实现 ###

![在这里插入图片描述][2cc54abb05004616b6bd3c918c27a216.png]  
定义三个类：`MyLinkList`用于LinkList成员变量和成员方法的定义、`Test`用于测试、`ListIndexOutException`用于定义越界异常

#### ListIndexOutException类 ####

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

#### MyLinkList类 ####

public class MyLinkList {
        
        
        static class ListNode {
        
            public int val;
            public ListNode prev;
            public ListNode next;
    
            public ListNode(int val) {
        
                this.val = val;
            }
        }
    
        //头结点
        public ListNode head;
        //尾结点
        public ListNode last;
    
        //头插法
        public void addFirst(int data) {
        
            ListNode node = new ListNode(data);
    
            if (head == null) {
        
                head = node;
                last = node;
            } else {
        
                node.next = head;
                head.prev = node;
                head = node;
            }
    
        }
    
        //尾插法
        public void addLast(int data) {
        
            ListNode node = new ListNode(data);
            if (head == null) {
        
                last = node;
                head = node;
            } else {
        
                last.next = node;
                node.prev = last;
                last = last.next;
            }
    
        }
    
        //返回某个下标的结点
        public ListNode findIndex(int index) {
        
            ListNode cur = head;
            while (index != 0) {
        
                cur = cur.next;
                index--;
            }
            return cur;
        }
    
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index, int data) {
        
            if (index < 0 || index > this.size()) {
        
                throw new ListIndexOutOfException();
            }
            if (index == 0) {
        
                addFirst(data);
                return;
            }
            if (index == size()) {
        
                addLast(data);
                return;
            }
            ListNode node = new ListNode(data);
            ListNode cur = findIndex(index);
            cur.prev.next = node;
            node.prev = cur.prev;
            node.next = cur;
            cur.prev = node;
        }
    
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key) {
        
            ListNode cur = this.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;
                        return;
                    }
                    cur.prev.next = cur.next;
                    if (cur == last) {
        
                        last = last.prev;
                        return;
                    }
                    cur.next.prev = cur.prev;
                    return;
                }
                cur = cur.next;
            }
        }
    
        //删除所有值为key的节点
        public void removeAllKey(int key) {
        
            ListNode tmp = head;
            while (tmp != null) {
        
                remove(key);
                tmp = tmp.next;
            }
    
        }
    
        //得到单链表的长度
        public int size() {
        
            ListNode cur = this.head;
            int length = 0;
            while (cur != null) {
        
                cur = cur.next;
                length++;
            }
            return length;
        }
    
        //遍历打印
        public void display() {
        
            ListNode cur = this.head;
            while (cur != null) {
        
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    
        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;
        }
    }

#### Test类 ####

public class Test {
        
        public static void main(String[] args) {
        
            //尾插法测试
            MyLinkList myLinkList2 = new MyLinkList();
            myLinkList2.addLast(1);
            myLinkList2.addLast(2);
            myLinkList2.addLast(3);
            myLinkList2.addLast(4);
            myLinkList2.display();
    
            //头插法测试
            MyLinkList myLinkList1 = new MyLinkList();
            myLinkList1.addFirst(1);
            myLinkList1.addFirst(2);
            myLinkList1.addFirst(3);
            myLinkList1.addFirst(4);
            myLinkList1.display();
    
            //addIndex测试
            System.out.println("addIndex测试");
            myLinkList1.addIndex(0, 5);
            myLinkList1.display();
            myLinkList1.addIndex(5, 0);
            myLinkList1.display();
            myLinkList1.addIndex(3, 99);
            myLinkList1.display();
    
            //remove测试
            System.out.println("remove测试");
            myLinkList1.remove(5);
            myLinkList1.display();
            myLinkList1.remove(0);
            myLinkList1.display();
            myLinkList1.remove(99);
            myLinkList1.display();
    
            //emoveAllKey测试
            System.out.println("removeAllKey测试");
            myLinkList1.addFirst(4);
            myLinkList1.addLast(1);
            myLinkList1.addIndex(1, 2);
            myLinkList1.display();
            myLinkList1.removeAllKey(4);
            myLinkList1.display();
            myLinkList1.removeAllKey(1);
            myLinkList1.display();
            myLinkList1.removeAllKey(2);
            myLinkList1.display();
        }
    }

#### 测试结果 ####

![在这里插入图片描述][b2e55c18f56e448293a2c4f3ac8ce93d.png]

[2cc54abb05004616b6bd3c918c27a216.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/3fab1dacdf3f45db9f8450ea0a6c0075.png
[b2e55c18f56e448293a2c4f3ac8ce93d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/4ec7e5f16e8d4c3b93f0e141704b5923.png