数据结构——【链表】

r囧r小猫 2022-05-09 02:50 400阅读 0赞

### 最基础的动态数据结构：链表 ###

Java中线性数据结构包括：数组、栈、队列【这三者底层都是基于动态数组实现的，实现动态的机制依靠resize()动态扩容】、链表【真正的动态数据结构】。

链表可以分为单向链表和双向链表。链表中的数据都存储在Node节点中，链表与链表之间的连接依靠next指针

Class Node{
        //存放数据
        E e;
        //指向当前节点的下一个节点
        Node next;
    }

**为什么说链表是真正的动态数据结构呢？**

链表不像数组，需要在初始化时候申明容量。链表中每一个节点都是一个Node对象，存放着数据和指向下一个Node的引用，在最后一个Node中，next为Null，链表不需要考虑和处理固定容量的问题，自然就不需要resize()了。

对于链表的特点，综合而言：

**优点**：真正的动态数据结构，不需要处理固定容量的问题

**缺点**：不像数组一样可以通过Index直接定位元素，丧失了随机访问的能力，从底层来说，数组开辟的空间在内存中是连续分布的，所以我们可以直接通过index的偏移直接计算出响应数据所存储的内存地址，直接通过O(1)即可取得元素。但是链表是通过next引用连接的，每一个Node所在的内存地址是不连续的，我们只能通过next来找到对应的元素。

下面我们来设计一个单向链表

使用了链表的虚拟头节点dummyHead，这样不需要对addFirst()进行特殊处理

package cn.itcats.linkedlist;
    
    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(null,null);
            size = 0;
        }
    
        //获得链表中元素个数
        public int getSize(){
            return size;
        }
    
        //判断链表是否为空
        public boolean isEmpty(){
            return size == 0 ;
        }
    
        //在链表的index位置添加新元素e
        public void add(int index ,E e){
            //对index进行判断
            if(index < 0 && index > size){
                throw new IllegalArgumentException("index不合法");
            }
                Node prev = dummyHead;
                //当遍历到插入索引的前一个索引
                for(int i = 0 ;i < index ; i++){
                    //prev指向下一个元素(index)
                    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){
            if(index < 0 || index >= size){
                throw new IllegalArgumentException("index不合法");
            }
            //从dummyHead的下一个节点遍历
            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("index不合法");
            }
            //找到第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;
        }
    
        /**
         * 在链表头部添加新的元素
         */
        public void addFirst(E e){
            add(0,e);
        }
    
        //在链表尾部添加元素
        public void addLast(E e){
            add(size,e);
        }
    
        //删除节点
        public E remove(int index){
            if(index < 0 || index >= size){
                throw new IllegalArgumentException("index不合法");
            }
            Node prev = dummyHead;
            for(int i = 0 ; i < index ;i++){
                //prev此时指向的是被删除节点的前一个位置
                prev = prev.next;
            }
            //需要被删除的节点
            Node removeNode = prev.next;
            prev.next = removeNode.next;
            removeNode.next = null;
            size --;
            return removeNode.e;
        }
    
        //从链表中删除第一个元素,返回删除的元素
        public E removeFirst(){
           return remove(0);
        }
    
        //从链表中删除最后一个元素,返回删除的元素
        public E removeLast(){
            return remove(size -1);
        }
    
    
        //遍历链表
        @Override
        public String toString(){
            StringBuilder sb = new StringBuilder();
            for(Node cur = dummyHead.next ; cur != null ; cur = cur.next)
                sb.append(cur+" -->");
            sb.append("NULL");
            return sb.toString();
        }
    }

测试方法

package cn.itcats.linkedlist;
    
    public class Test {
        public static void main(String[] args) {
            LinkedList<Integer> linked = new LinkedList<>();
            for(int i = 0 ; i < 5 ; i++){
                linked.addFirst(i);
                System.out.println(linked);
            }
            linked.add(2,111);
            System.out.println(linked);
    
            linked.remove(3);
            System.out.println(linked);
        }
    }

### 链表的时间复杂度分析 ###

添加操作：

addLast(e)            O(n)

addFirst(e)            O(1)

add(index,e)          O(n)

删除操作：

removeLast(e)            O(n)

removeFirst(e)            O(1)

add(index,e)                O(n)

修改操作        set(index,e)     O(n)

查找操作

get(index)               O(n)