数据结构之链表[Java]

灰太狼 2023-07-24 05:37 13阅读 0赞

/** * @ClassName: LinkedList * @Author: Leo * @Description: 链表 * @Date: 4/9/2020 12:43 PM */
    public class LinkedList<E> { 
        /** * 维护的内部Node节点 */
        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;
        //链表内元素数量
        private int size;
    
        public LinkedList() { 
            dummyHead = new Node();
            size = 0;
        }
    
        /** * 获取链表元素数量 * * @return */
        public int getSize() { 
            return size;
        }
    
        /** * 判断链表是否为空 * * @return */
        public boolean isEmpty() { 
            return size == 0;
        }
    
        /** * 向指定索引添加元素 * * @param index * @param 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++;
        }
    
        /** * 头插法 * * @param e */
        public void addFirst(E e) { 
            add(0, e);
        }
    
        /** * 尾插法 * * @param e */
        public void addLast(E e) { 
            add(size, e);
        }
    
        /** * 获取索引位置的元素 * * @param index * @return */
        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;
        }
    
        /** * 获取首部元素 * * @return */
        public E getFirst() { 
            return get(0);
        }
    
        /** * 获取尾部元素 * * @return */
        public E getLast() { 
            return get(size - 1);
        }
    
        /** * 设置index位置的元素 * * @param index * @param 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 * * @param e * @return */
        public boolean contains(E e) { 
            Node cur = dummyHead.next;
            while (cur != null) { 
                if (cur.e.equals(e)) { 
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
    
        /** * 删除index位置的元素 * * @param index * @return */
        public E remove(int index) { 
            if (index < 0 || index >= size) { 
                throw new IllegalArgumentException("Remove failed. Index is illegal.");
            }
    
            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 void removeFirst() { 
            remove(0);
        }
    
        /** * 删除尾部元素 */
        public void removeLast() { 
            remove(size - 1);
        }
    
        /** * 删除指定元素 * * @param e */
        public void removeElement(E e) { 
            Node prev = dummyHead;
            while (prev != null) { 
                if (prev.next.e.equals(e)) { 
                    break;
                }
                prev = prev.next;
            }
    
            if (prev.next != null) { 
                Node delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
                size--;
            }
        }
    
        @Override
        public String toString() { 
            StringBuilder sb = new StringBuilder();
            Node cur = dummyHead.next;
            while (cur != null) { 
                sb.append(cur + "->");
                cur = cur.next;
            }
            sb.append("NULL");
            return sb.toString();
        }
    }