1.链表介绍

　　前面我们已经介绍了向量，向量是基于数组进行数据存储的线性表。今天，要介绍的是线性表的另一种实现方式---链表。

　　链表和向量都是线性表，从使用者的角度上依然被视为一个线性的列表结构。但是，链表内部存储数据的方式却和向量大不相同：链表的核心是节点。节点存储"数据"的同时还维护着"关联节点的引用"。要理解链表，首先必须理解链表的内部节点结构。

　　最简单的链表结构是单向链表，单向链表中的内部节点存储着数据(data)和其关联的下一个节点的引用(next)。

　　一个逻辑上存储了【a，b，c】三个元素的链表，长度为3，三个元素分别被三个节点存储。

2.链表ADT介绍

　　链表作为线性表的一种，和向量一样实现了List接口。

/**
 * 列表ADT 接口定义
 */
public interface List <E> {

    
     * @return 返回当前列表中元素的个数
     */
    int size();

    
     * 判断当前列表是否为空
     *  如果当前列表中元素个数为0，返回true；否则，返回false
     boolean isEmpty();

    
     * 返回元素"e"在列表中的下标值
     * @param e     查询的元素"e"
     *       返回"obj"元素在列表中的下标值;
     *               "obj"不存在于列表中，返回-1;
      indexOf(E e);

    
     * 判断元素"e"是否存在于列表中
     *       返回"true"代表存在，返回"false"代表不存在;
      contains(E e);

    
     * 在列表的末尾插入元素"e"
     *  e 需要插入的元素
     *   插入成功，返回true；否则返回false
     *  add(E e);

    
     * 在列表的下标为"index"位置处插入元素"e"
     *  index 插入位置的下标
     *  e     需要插入的元素
     void add( index,E e);

    
     *  从列表中找到并且移除"e"对象
     *  e   需要被移除的元素"e"
     *       找到并且成功移除返回true；否则返回false
      remove(E e);

    
     * 移除列表中下标为"index"位置处的元素
     *  index  需要被移除元素的下标
     *       返回被移除的元素
     */
    E remove( index);

    
     * 将列表中下标为"index"位置处的元素替代为"e"
     *  index 需要被替代元素的下标
     *  e     新的元素
     *       返回被替代的元素
     
    E set(
     * 返回列表中下标为"index"位置处的元素
     *  index 查找元素的"index"元素
     *       返回找到的元素
     
    E get(
     * 清除列表中所有元素
     * void clear();

    
     * 获得迭代器
     * 
    Iterator<E> iterator();
}

3.链表实现细节

　　由于使用java作为实现的语言，因此在设计上参考了jdk自带的链表数据结构：java.util.LinkedList类。

　　LinkedList是一个双端双向链表，因此我们的链表实现也是一个双端双向链表。相比单向链表，双端双向链表功能更加强大，当然也稍微复杂一点。

3.1 链表内部节点

　　双端双向链表内部节点的特点是：每个节点同时拥有该节点"前驱"和"后继"的节点引用(双向)。

　　需要注意的是，对于内部节点两端的引用在不同地方存在着不同称呼。如"前驱(predecess)"/"后继(success)"、"前一个(previous)"/"下一个(next)"、"左(left)/右(right)"等。不必纠结于名词叫法，用自己的方式理解就行。"重要的不是它们叫什么，而是它们是什么"。

　　个人认为"左(left)/右(right)"的称呼比较形象(比较像一群小人，手拉手)，所以在这篇博客中统一使用这种叫法。同时为了描述的简洁，下文中的"链表"默认指的就是"双端双向链表"。

链表内部节点结构示意图：

　　在我们的链表实现中，将内部节点抽象为一个私有的静态内部类。首先我们有：

class LinkedList <E> implements List <E>{ 
   
     * 链表内部节点类
     private static class Node <T>{
        
         * 左边关联的节点引用
         * 
        Node<T> left;

        
         * 右边关联的节点引用
         *  right;

        
         * 节点存储的数据
         * 
        T data;

        //===================================内部节点 构造函数==================================
        private Node() {}

         Node(T data) {
            this.data = data;
        }

        
         * 将一个节点作为"当前节点"的"左节点" 插入链表
         *  node  需要插入的节点
         * */
        void linkAsLeft(Node<T> node){
            :::先设置新增节点的 左右节点
            node.left = this.left;
            node.right = ;

            :::将新增节点插入 当前节点和当前节点的左节点之间
            this.left.right = node;
            this.left = node;
        }

        
         * 将一个节点作为"当前节点"的"右节点" 插入链表
         * void linkAsRight(Node<T>;
            node.right = .right;

            :::将新增节点插入 当前节点和当前节点的左节点之间
            node.right.left = node;
            node.right =
         * 将"当前节点"移出链表
         *  unlinkSelf(){
            :::令当前链表的 左节点和右节点建立关联
            this.left.right = .right;
            :::令当前链表的 右节点和左节点建立关联
            this.right.left = .left;
            
            :::这样,当前节点就从链表中被移除了(同时,作为私有的内部类,当前节点不会被其它对象引用,很快会被GC回收)
        }
    }
}

　　我们在内部节点类中提供了几个常用的方法，为接下来的链表操作提供基础。

linkAsLeft操作举例说明：

　　已知链表中存在【a，c】两个节点，现在c节点调用linkAsLeft方法，将b节点作为c的左节点插入链表(这时，c节点就是this)。(linkAsRight?原理类似)

linkAsLeft操作示意图：

unlinkSelf操作举例说明：

　　已知链表中存在【a，b，c】三个节点，现在b节点调用unlinkSelf方法，将b节点自身移出链表(这时，b节点就是this)。

unlinkSelf操作示意图：

?　　

　　可以看到插入和移除操作对于节点左右引用的改变是互逆的。

　　移除操作执行完成后，虽然b节点还持有a，c两节点的引用，但是Node作为封装的私有内部类，可以确保b节点本身不会被其它对象引用，很快会被GC回收。

3.2 链表基本属性

　　链表作为一个数据结构容器，拥有一些必备的属性。

（编辑：新余站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!