玩转数据结构（三）实现链表LinkedList

太过爱你忘了你带给我的痛 2022-05-21 08:25 192阅读 0赞

链表是一种线性数据结构，是由一个个节点构成，节点之间由指针（引用）连接起来；

凡是谈到链表就要和数组来做比较。那来比较一下数组和链表的区别：

1.  数组要求的内存连续，而链表不需要
2.  数组的增删比较复杂，需要涉及数组元素的移动操作，而链表的增删只需要更改指针的指向即可
3.  数组按照索引查询的时间复杂度为O（1），而链表查找一个元素时需要从头结点开始遍历查找
4.  数组存储内容没有浪费额外空间，而链表花费空间存储了指针（引用）

下面使用Java实现自己的链表。

### 实现代码 ###

/**
     * 链表
     * @param <E> 泛型
     */
    public class LinkedList<E> {
        /**
         * 链表结点的定义
         */
        private class Node {
            private E e;
            private 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;
        }
    
        public int getSize() {
            return size;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        public void addFirst(E e) {
            add(0, e);
        }
    
        public void addLast(E e) {
            add(size, e);
        }
    
        public void add(int index, E e) {
            //判断index合法性
            if(index < 0 || index > size) {
                throw new IllegalArgumentException("add Failed! index is illegal!");
            }
    
            //查找指定索引的前一个结点的索引
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }
    
    //        Node node = new Node(e);
    //        node.next = prev.next;
    //        prev.next = node;
            prev.next = new Node(e, prev.next);
            size++;
        }
    
        //获取指定下标的元素
        public E get(int index) {
            //判断index合法性
            if(index < 0 || index >= size) {
                throw new IllegalArgumentException("get Failed! index is illegal!");
            }
            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);
        }
    
        //更新某位置的元素为新元素
        public void set(int index, E e) {
            //判断index合法性
            if(index < 0 || index >= size) {
                throw new IllegalArgumentException("set Failed! index is illegal!");
            }
    
            Node cur = dummyHead.next;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
    
            cur.e = e;
        }
    
        //判断链表中是否包含某元素
        public boolean contains(E e) {
            for(Node cur = dummyHead.next; cur != null; cur = cur.next) {
                if(cur.e.equals(e)) {
                    return true;
                }
            }
    
            return false;
        }
    
        //删除指定位置的元素
        public void remove(int index) {
            //判断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 delNode = prev.next;
            prev.next = delNode.next;
            delNode = null;
    
            size--;
        }
    
        public void removeFirst() {
            remove(0);
        }
    
        public void removeLast() {
            remove(size - 1);
        }
    
        //删除指定元素e
        public void removeElement(E e) {
            Node prev = dummyHead;
            while(prev.next != null) {
                if(prev.next.e.equals(e)) {
                    break;
                } else {
                    prev = prev.next;
                }
            }
    
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;
        }
    
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            for(Node cur = dummyHead.next; cur != null; cur = cur.next) {
                res.append(cur.e + "->");
            }
    
            res.append("NULL");
    
            return res.toString();
        }
    
        /**
         * 时间复杂度分析：
         * addFirst:O(1)
         * addLast:O(n)
         *
         * removeFirst:O(1)
         * removeLast:0(n)
         *
         * set: 0(n)
         *
         * getFirst O(1)
         * getLast O(n)
         * 对头查：O(1)
         *
         * 增删改查均为0(n)
         *
         */
    }

### 测试代码 ###

public static void main(String[] args) {
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < 10; i++) {
                list.addLast(i);
            }
            System.out.println(list);
    
            System.out.println("链表中元素个数：" + list.getSize());
            System.out.println("链表中首元素：" + list.getFirst());
            System.out.println("链表中尾元素：" + list.getLast());
            System.out.println("链表获取下标为2的元素：" + list.get(2));
        }

### 结果 ###

0->1->2->3->4->5->6->7->8->9->NULL
    链表中元素个数：10
    链表中首元素：0
    链表中尾元素：9
    链表获取下标为2的元素：2