Java自定义链表

一时失言乱红尘 2022-10-02 12:45 219阅读 0赞

实现代码如下:

public class LinkedList<E> {
    
        private class Node{
            public E e;
            public Node next;
    
            public Node(E e , Node next){
                this.e = e;
                this.next = next;
            }
    
            public Node(E e){
                this(e, null);
            }
    
            public Node(){
                this(null,null);
            }
    
            @Override
            public String toString(){
                return e.toString();
            }
        }
    
        private Node dummyHead;
        int size;
    
        public LinkedList(){
            dummyHead = new Node(null,null);
            size = 0;
        }
    
        // 获取链表中的元素个数
        public int getSize() { return size; }
    
        // 判断链表是否为空
        public boolean isEmpty() {
            return size == 0;
        }
    
        // 在链表头添加新的元素e
        public void addFirst(E e){
            add(0, e);
        }
    
        // 在链表中指定位置添加元素
        // 不是常用操作
        public void add(int index, E e) {
            if (index < 0 || index > size)
                throw new IllegalArgumentException("Add failed. Illegal index.");
    
            Node prev = dummyHead;
            for (int i = 0; i < index; i++)
                prev = prev.next;
    
            prev.next = new Node(e, prev.next);
            size++;
        }
    	
    	    // 删除指定index元素
        public E romove(int index){
            if (index < 0 || index >= size)
                throw new IllegalArgumentException("remove failed. Illegal index.");
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }
    
            Node retNode = prev.next;
            prev.next = retNode.next;
            retNode.next = null;
            size --;
    
            return retNode.e;
        }
    
        // 从链表中删除第一个元素, 返回删除的元素
        public E removeFirst(){
            return romove(0);
        }
    
        // 从链表中删除最后一个元素, 返回删除的元素
        public E removeLast(){
            return romove(size - 1);
        }
    
    
        // 获得链表的第index(0-based)个位置的元素
        public E get(int index){
            if (index < 0 || index >= size)
                throw new IllegalArgumentException("Get failed. Illegal index.");
    
            Node cur = dummyHead.next;
            for (int i = 0 ; i < index ; i++)
                cur = cur.next;
            return cur.e;
        }
    
        // 获得链表的第一个元素
        public E getFirst(){
            return get(0);
        }
    
        // 获得链表最后一个元素
        public E getLast(){
            return get(size - 1);
        }
    
        // 修改链表的第index个位置的元素为e
        public void set(int index ,E e){
            if (index < 0 || index >= size)
                throw new IllegalArgumentException("Set failed. Illegal index.");
    
            Node cur = dummyHead.next;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            cur.e = e;
        }
    
        // 查找链表中是否有元素e
        public boolean contains(E e){
    
            Node cur = dummyHead.next;
            while (cur != null){
                if (cur.e.equals(e)){
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
    
        @Override
        public String toString(){
    
            StringBuilder res = new StringBuilder();
    
            for (Node cur = dummyHead.next; cur != null ; cur = cur.next)
                res.append(cur + "->");
            res.append("NULL");
            
            return res.toString();
        }
    
    
    }

测试方法如下:

public static void main(String[] args) {
    
            LinkedList<Integer> linkedList = new LinkedList<>();
            for (int i = 0; i < 8; i++) {
                linkedList.addFirst(i);
                System.out.println(linkedList.toString());
            }
    
            linkedList.add(4, 998);
            System.out.println(linkedList);
        }

测试结果如图:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU5NDA1Ng_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU5NDA1Ng_size_16_color_FFFFFF_t_70]: /images/20220112/7f70e9e417b2405faabed89713cdec92.png