链表（Linked List）

在分析链表之前，我们先来对之前的动态数组、栈、队列总结一下：
（1）底层依托于静态数组
（2）依靠resize解决固定容量问题

image.png
（3）是一种假的的动态数据结构
1.什么是链表

可以从以下两个部分来理解什么是链表:
（1）最简单的动态数据结构，是一种真正的动态数据结构；
（2）是一种数据的存储方式,数据存储在"节点"（Node）中

1.1结构基本代码：

class Node{
  E e;
  Node next;
}

1.2 图示如下：

链表结构.png
1.3 优点、缺点*
优点：真正的动态，不需要处理固定容量的问题
缺点：丧失了随机访问的能力，也就是不能通过索引进行访问，只能next来进行查找
1.4数组与链表的对比
image.png

** 1.5 基本的链表节点结构代码：**
新建一个package（LinkedList），然后新建一个类LinkedList,在该类中封装一个私有的节点.

package LinkedList;

public class LinkedList<E> {
    //将Node节点设计成私有的类中类
    private class Node<E> {
        public E e;
        public Node next;


        //两个参数的构造函数

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        //一个参数的构造函数
        public Node(E e) {
            this.e = e;
            this.next = null;
        }

        //无参构造函数
        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }
}

在本小节中先是简单了解了一下理论知识，然后把基本的链表节点结构使用代码来实现，下一小节我们继续来学习如何如何在链表中添加元素。