链表（1）

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

掌握链表有助于学习更加复杂的数据结构，例如：二叉树、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;
    }