我们以前学过的线性数据结构底层原理都是依托静态数组来实现的，今天我们讲学习一个最简单的动态数据结构---->链表！

掌握链表有助于学习更加复杂的数据结构，例如：二叉树、trie

链表的优点是不需要处理固定的问题，真正的动态，缺点是丧失了随机访问的能力

 在生活中可以形象表示链表的东西有很多，比如自行车车链

在数据结构中我们学习的是他们的最基本的操作增删改查，下面让我们来逐步了解链表的实现

增加：

1.在头部添加

 2.在尾部添加

 3.在中间进行添加：

这种添加情况需要对在头结点进行添加时进行特别处理，比如判断头结点是否为空等

进行虚拟头结点进行添加操作：

 public void addHead(T ele) {this.add(0, ele);}public void addTail(T ele) {this.add(this.size, ele);}// 在指定位置添加结点, 关键点: 找到待插入位置的前一个结点public void add(int index, T ele) {if (index < 0 || index > this.size) {throw new IllegalArgumentException("index is invalid!");}Node node = new Node(ele);// 给链表增加一个虚拟头结点, 解决在链表的头部添加时的特殊处理Node dummyHead = new Node(null);dummyHead.next = head;Node prev = dummyHead;for (int i = 0; i < index; i++) {prev = prev.next;}node.next = prev.next;prev.next = node;// 更新头结点head = dummyHead.next;this.size++;}

在增加和删除的时候需要知道操作位置上前节点pre,删除和查找不需要

删除：

在头部进行删除： 在尾部进行删除：

 在中间进行删除：

 使用虚拟头结点则不需要对头结点进行特殊操作

//将链表中的元素进行删除public void delete(int index) {if (index < 0 || index >= this.size) {}//无虚拟头结点
//        if (index == 0) {
//            Node delnode = head;
//            head = delnode.next;
//            delnode.next = null;
//            this.size--;
//        } else {
//            Node pre = head;
//            Node cur = pre.next;
//            for (int i = 1; i < index; i++) {
//                pre = pre.next;
//                cur=cur.next;
//            }
//            Node delnode =cur;
//            pre.next = delnode.next;
//            delnode.next = null;
//            this.size--;
//            cur = cur.next;//有虚拟头节点Node dummyNode=new Node(null);dummyNode.next=head;Node pre=dummyNode;Node cur=pre.next;for (int i = 0; i < index; i++) {pre=pre.next;cur=cur.next;}Node delnode =cur;pre.next = delnode.next;delnode.next = null;this.size--;cur = cur.next;}

在链表中也有一些方法需要让我们掌握，一下代码仅供参考：

      //根据索引找对应的元素public T get(int index){if(index<0||index>=this.size){return null;}Node cur=head;for (int i = 0; i < index; i++) {cur=cur.next;}return cur.ele;}
//获取头节点的元素public T getFirst(){return get(0);}//获取尾结点的元素public T getLast(){return get(this.size-1);}//判断是否包含该元素public boolean contain(T ele){Node cur=head;for (int i = 0; i < this.size; i++) {if(cur.ele.compareTo(ele)==0){return true;}cur=cur.next;}return false;}//将链表中的某个元素进行替换public void set(T ele,int index) {if(index<0||index>=this.size){}Node cur=head;for (int i = 0; i < index; i++) {cur=cur.next;}cur.ele=ele;}