使用链式存储结构实现线性表（单链表、双链表）

@Yi-Xing  2020-03-01 0 评论 0 浏览
 

一、线性表

  线性表分为顺序存储结构和链式存储结构，上一篇讲解了使用顺序存储结构实现线性表，下面讲解使用链式存储结构实现线性表。

二、什么是链式存储结构

  链式存储结构，又叫链接存储结构。在计算机中用一组任意的存储单元存储线性表的数据元素，它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域；存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。

三、单链表

  单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

1、定义结点

  单链表的结点由元素(数据元素的映象) + 指针(指示后继元素存储位置)组成，由于存储的数据类型不确定，我们使用泛型来表示未确定的数据类型。

/**
 * 单链表的结点
 **/
public class ListNode<T> {
    /**
     * 存储数据
     */
    protected T data;
    /**
     * 存储后继
     */
    protected ListNode<T> next;

    /**
     * 创建结点并初始化值
     */
    public ListNode(T data) {
        this.data = data;
    }
}

2、实现单链表

  单链表也实现上一篇定义的 MyList 接口。first 和 last 分别存储单链表的开头和结尾，尾结点的后继为 null；size 表示单链表的长度，即结点的个数。

/**
 * 单链表
 **/
public class SingleLinkedList<T> implements MyList<T> {

    /**
     * 开头（头结点）
     */
    public ListNode<T> first;
    /**
     * 结尾（尾结点）
     */
    private ListNode<T> last;
    /**
     * 链表的长度，结点的个数
     */
    private int size = 0;
}
1）添加结点

  向单链表中添加结点分两种情况：

  1. 单链表为空：则新加的结点，既为单链表的头结点又为单链表的尾结点。
  2. 单链表不为空：直接将结点追加到单链表的尾结点，并更新单链表尾结点的值。
    @Override
    public void add(T value) {
        // 如果单链表为空，则将结点赋给单链表的头结点和尾结点
        if (first == null) {
            first = new ListNode<>(value);
            last = first;
        } else {
            // 如果单链表有结点，则直接向后追加并更新尾结点的值
            last.next = new ListNode<>(value);
            last = last.next;
        }
	// 更新单链表的长度
        size++;
    }
2）插入结点

  向单链表中插入结点分三种情况：

  1. 向头部添加结点：更换单链表的头结点，并将新结点的后继指向单链表的原头结点。
  2. 向尾部添加结点：直接调用 add 方法即可。
  3. 向单链表中添加结点：先遍历链表，找到结点应插入的位置。然后将新结点的后继指向当前结点，将当前结点的原前驱的后继指向新结点即可。
    @Override
    public void insert(int index, T value) {
        // 如果下标等于0，则更换单链表的头结点
        if (index == 0) {
            ListNode<T> newNode = new ListNode<>(value);
            newNode.next = first;
            first = newNode;
            // 更新单链表的长度
            size++;
        } else if (index == size) {
            // 如果下标等于size，则是向单链表的末尾添加结点，直接调用 add 方法即可
            add(value);
        } else if (index > -1 && index < size) {
            // 如果下标大于-1且小于元素的个数，则表示向单链表中插入结点
            ListNode<T> newNode = new ListNode<>(value);
            // 指针指向的结点的索引
            int i = 0;
            // p是遍历链表的指针
            ListNode<T> p = first;
            // pre记录p的前驱（前一个元素）
            ListNode<T> pre = null;
            while (p != null) {
                // 找到结点后，将新结点的后继指向p，将p的原前驱的后继指向新结点即可
                if (i == index) {
                    pre.next = newNode;
                    newNode.next = p;
                    // 更新单链表的长度
                    size++;
                    break;
                }
                // 更新结点的值，向后遍历
                pre = p;
                p = p.next;
                // 下标自加
                i++;
            }
        }
    }
3）删除结点

  删除元素的方式分为：根据下标删除元素和根据元素值删除元素。

  根据值删除结点，首先遍历单链表查找第一个和该值相同的结点，然后将其删除。

  1. 结点不存在：直接退出。
  2. 结点为头结点：用该结点的后继覆盖单链表的头结点即可。
  3. 结点为中间结点：将该结点的前驱指向该结点的后继。
  4. 结点为尾结点：用该结点的前驱覆盖单链表的尾结点即可。

  我们在删除结点时，会用到该结点的前驱和后继，而单链表只有后继的指针，所以我们在遍历单链表时，需要将当前结点的前驱保存起来。

    @Override
    public void delete(T value) {
        // p是遍历链表的指针
        ListNode<T> p = first;
        // pre记录p的前驱（前一个元素）
        ListNode<T> pre = null;
        // 遍历链表
        while (p != null) {
            if (p.data.equals(value)) {
                // 结点为头结点
                if (p == first) {
                    first = first.next;
                } else if (p == last) {
                    // 结点为尾结点
                    last = pre;
                } else {
                    // 结点为中间结点
                    pre.next = p.next;
                }
                size--;
                break;
            }
            // 更新结点的值，向后遍历
            pre = p;
            p = p.next;
        }
    }

  根据下标删除结点和根据值删除结点类似，只需在遍历单链表时，记录下标值即可。

    @Override
    public void delete(int index) {
        // 首先判断下标是否合法
        if (index < 0 || index >= size) {
            return;
        }
        // 指针指向的节点的索引
        int i = 0;
        // p是遍历链表的指针
        ListNode<T> p = first;
        // pre记录p的前驱（前一个元素）
        ListNode<T> pre = null;
        while (p != null) {
            if (i == index) {
                // 结点为头结点
                if (p == first) {
                    first = first.next;
                } else if (p == last) {
                    // 结点为尾结点
                    last = pre;
                } else {
                    // 结点为中间结点
                    pre.next = p.next;
                }
                size--;
                break;
            }
            // 更新结点的值，向后遍历
            pre = p;
            p = p.next;
            // 下标自加
            i++;
        }
    }
4）打印单链表

  重写单链表的 toString 方法，将单链表中的所有结点的值组成字符串即可。

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        ListNode<T> p = first;
        // 遍历单链表
        while (p != null) {
            sb.append(p.data);
            p = p.next;
            if (p != null) {
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }
5）其他方法

  其他的方法的实现比较简单，这里不多做解释，SingleLinkedList 的全部代码如下：

/**
 * 单链表
 **/
public class SingleLinkedList<T> implements MyList<T> {

    /**
     * 开头（头结点）
     */
    public ListNode<T> first;
    /**
     * 结尾（尾结点）
     */
    private ListNode<T> last;
    /**
     * 链表的长度，结点的个数
     */
    private int size = 0;

    @Override
    public void add(T value) {
        // 如果单链表为空，则将结点赋给单链表的头结点和尾结点
        if (first == null) {
            first = new ListNode<>(value);
            last = first;
        } else {
            // 如果单链表有结点，则直接向后追加并更新尾结点的值
            last.next = new ListNode<>(value);
            last = last.next;
        }
        // 更新单链表的长度
        size++;
    }

    @Override
    public void insert(int index, T value) {
        // 如果下标等于0，则更换单链表的头结点
        if (index == 0) {
            ListNode<T> newNode = new ListNode<>(value);
            newNode.next = first;
            first = newNode;
            // 更新单链表的长度
            size++;
        } else if (index == size) {
            // 如果下标等于size，则是向单链表的末尾添加结点，直接调用 add 方法即可
            add(value);
        } else if (index > -1 && index < size) {
            // 如果下标大于-1且小于元素的个数，则表示向单链表中插入结点
            ListNode<T> newNode = new ListNode<>(value);
            // 指针指向的结点的索引
            int i = 0;
            // p是遍历链表的指针
            ListNode<T> p = first;
            // pre记录p的前驱（前一个元素）
            ListNode<T> pre = null;
            while (p != null) {
                // 找到结点后，将新结点的后继指向p，将p的原前驱的后继指向新结点即可
                if (i == index) {
                    pre.next = newNode;
                    newNode.next = p;
                    // 更新单链表的长度
                    size++;
                    break;
                }
                // 更新结点的值，向后遍历
                pre = p;
                p = p.next;
                // 下标自加
                i++;
            }
        }
    }

    @Override
    public void delete(T value) {
        // p是遍历链表的指针
        ListNode<T> p = first;
        // pre记录p的前驱（前一个元素）
        ListNode<T> pre = null;
        // 遍历链表
        while (p != null) {
            if (p.data.equals(value)) {
                // 结点为头结点
                if (p == first) {
                    first = first.next;
                } else if (p == last) {
                    // 结点为尾结点
                    last = pre;
                } else {
                    // 结点为中间结点
                    pre.next = p.next;
                }
                size--;
                break;
            }
            // 更新结点的值，向后遍历
            pre = p;
            p = p.next;
        }
    }

    @Override
    public void delete(int index) {
        // 首先判断下标是否合法
        if (index < 0 || index >= size) {
            return;
        }
        // 指针指向的节点的索引
        int i = 0;
        // p是遍历链表的指针
        ListNode<T> p = first;
        // pre记录p的前驱（前一个元素）
        ListNode<T> pre = null;
        while (p != null) {
            if (i == index) {
                // 结点为头结点
                if (p == first) {
                    first = first.next;
                } else if (p == last) {
                    // 结点为尾结点
                    last = pre;
                } else {
                    // 结点为中间结点
                    pre.next = p.next;
                }
                size--;
                break;
            }
            // 更新结点的值，向后遍历
            pre = p;
            p = p.next;
            // 下标自加
            i++;
        }
    }

    @Override
    public void update(int index, T value) {
        if (index < 0 || index >= size) {
            return;
        }
        int i = 0;
        ListNode<T> p = first;
        while (p != null) {
            if (i == index) {
                p.data = value;
                break;
            }
            p = p.next;
            i++;
        }
    }

    @Override
    public boolean contains(T target) {
        ListNode<T> p = first;
        while (p != null) {
            if (p.data.equals(target)) {
                return true;
            }
            p = p.next;
        }
        return false;
    }

    @Override
    public T at(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        int i = 0;
        ListNode<T> p = first;
        while (p != null) {
            if (i == index) {
                return p.data;
            }
            p = p.next;
            i++;
        }
        return null;
    }

    @Override
    public int indexOf(T value) {
        int i = 0;
        ListNode<T> p = first;
        while (p != null) {
            if (p.data.equals(value)) {
                return i;
            }
            p = p.next;
            i++;
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        ListNode<T> p = first;
        // 遍历单链表
        while (p != null) {
            sb.append(p.data);
            p = p.next;
            if (p != null) {
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    @Override
    public int getSize() {
        return size;
    }
}

四、双链表

  双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

1、定义结点

  双链表的结点由前驱指针(指示前驱元素存储位置) + 元素(数据元素的映象) + 后继指针(指示后继元素存储位置)组成，由于存储的数据类型不确定，我们使用泛型来表示未确定的数据类型。

/**
 * 双链表的结点
 **/
public class ListNode<T> {
    
    /**
     * 存储前驱（头指针）
     */
    protected ListNode<T> pre;
    /**
     * 存储数据
     */
    protected T data;
    /**
     * 存储后继（尾指针）
     */
    protected ListNode<T> next;
    /**
     * 创建结点并初始化值
     */
    public ListNode(T data) {
        this.data = data;
    }
}

2、实现双链表

  双链表与单链表最大的区别就是结点存储了前驱，为了方便操作双链表的头结点和尾结点不再存储元素称为哑元。

/**
 * 双链表
 **/
public class DoubleLinkedList<T> implements MyList<T> {

    /**
     * 开头（头结点）
     */
    protected ListNode<T> first = new ListNode<>(null);
    /**
     * 结尾（尾结点）
     */
    protected ListNode<T> last = new ListNode<>(null);
    /**
     * 链表的长度，结点的个数
     */
    protected int size = 0;
}
1）创建双链表

  创建双链表时，要为哑元的前驱或后继赋值，以免在运算时出现空指针。

    public DoubleLinkedList() {
        // 维护两个哑元做头尾
        this.first.next = last;
        this.last.pre = first;
    }
2）添加结点

  首先将尾哑元的前驱结点的后指针指向新结点，然后将新结点的头指针和尾指针分别指向尾哑元的前驱和尾哑元，最后将尾哑元的头指针指向新结点。

    @Override
    public void add(T value) {
        ListNode<T> newNode = new ListNode<>(value);
        // 将尾哑元的前驱结点的后指针指向新结点
        last.pre.next = newNode;
        // 新结点头指针指向尾哑元的前驱
        newNode.pre = last.pre;
        // 新结点尾指针指向尾哑元
        newNode.next = last;
        // 尾哑元头指针指向新结点
        last.pre = newNode;
        size++;
    }
3）插入结点

  因为有哑元的存在，插入结点时无需分多种情况讨论。首先遍历双链表找到指定结点，然后将新结点的头结点和尾结点分别指向当前结点的前驱和当前结点，最后将当前结点前驱的尾结点和当前结点的头结点指向新结点。

    @Override
    public void insert(int index, T value) {
        if (index > -1 && index <= size) {
            // 如果下标大于-1且小于元素的个数，则表示向双链表中插入结点
            ListNode<T> newNode = new ListNode<>(value);
            // 指针指向的结点的索引
            int i = 0;
            // p是遍历链表的指针
            ListNode<T> p = first.next;
            while (p != null) {
                // 找到结点后，将新结点的头结点和尾结点分别指向p的前驱和p
                // 然后更新p前驱的尾结点和p的头结点。
                if (i == index) {
                    newNode.pre = p.pre;
                    newNode.next = p;
                    p.pre.next = newNode;
                    p.pre = newNode;
                    // 更新单链表的长度
                    size++;
                    break;
                }
                // 更新结点的值，向后遍历
                p = p.next;
                // 下标自加
                i++;
            }
        }
    }
4）删除结点

  删除元素的方式分为：根据下标删除元素和根据元素值删除元素。

  根据值删除结点，首先遍历双链表查找第一个和该值相同的结点，然后将其前驱的尾结点指向当前结点的尾结点，后驱的头结点指向当前结点的头结点。

    @Override
    public void delete(T value) {
        ListNode<T> p = first.next;
        // 遍历双链表
        while (p != last) {
            if (p.data.equals(value)) {
                // 将上一个节点的尾指针指向下一个节点
                p.pre.next = p.next;
                // 将下一节点的头指针指向上一个节点
                p.next.pre = p.pre;
                // 当前指针赋空
                p.next = null;
                p.pre = null;
                size--;
                break;
            }
            p = p.next;
        }
    }

  根据下标删除结点和根据值删除结点类似，只需在遍历双链表时，记录下标值即可。

    @Override
    public void delete(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        // 指针指向的节点的索引
        int i = 0;
        ListNode<T> p = first.next;
        while (p != last) {
            if (i == index) {
                // 将上一个节点的尾指针指向下一个节点
                p.pre.next = p.next;
                // 将下一节点的头指针指向上一个节点
                p.next.pre = p.pre;
                // 当前指针赋空
                p.next = null;
                p.pre = null;
                size--;
                break;
            }
            p = p.next;
            i++;
        }
    }
5）其他方法

  其他的方法的实现和单链表相似，DoubleLinkedList 的全部代码如下：

/**
 * 双链表
 **/
public class DoubleLinkedList<T> implements MyList<T> {

    /**
     * 开头（头结点）
     */
    protected ListNode<T> first = new ListNode<>(null);
    /**
     * 结尾（尾结点）
     */
    protected ListNode<T> last = new ListNode<>(null);
    /**
     * 链表的长度，结点的个数
     */
    protected int size = 0;

    public DoubleLinkedList() {
        // 维护两个哑元做头尾
        this.first.next = last;
        this.last.pre = first;
    }

    @Override
    public void add(T value) {
        ListNode<T> newNode = new ListNode<>(value);
        // 将尾哑元的前驱结点的后指针指向新结点
        last.pre.next = newNode;
        // 新结点头指针指向尾哑元的前驱
        newNode.pre = last.pre;
        // 新结点尾指针指向尾哑元
        newNode.next = last;
        // 尾哑元头指针指向新结点
        last.pre = newNode;
        size++;
    }

    @Override
    public void insert(int index, T value) {
        if (index > -1 && index <= size) {
            // 如果下标大于-1且小于元素的个数，则表示向双链表中插入结点
            ListNode<T> newNode = new ListNode<>(value);
            // 指针指向的结点的索引
            int i = 0;
            // p是遍历链表的指针
            ListNode<T> p = first.next;
            while (p != null) {
                // 找到结点后，将新结点的头结点和尾结点分别指向p的前驱和p
                // 然后更新p前驱的尾结点和p的头结点。
                if (i == index) {
                    newNode.pre = p.pre;
                    newNode.next = p;
                    p.pre.next = newNode;
                    p.pre = newNode;
                    // 更新单链表的长度
                    size++;
                    break;
                }
                // 更新结点的值，向后遍历
                p = p.next;
                // 下标自加
                i++;
            }
        }
    }

    @Override
    public void delete(T value) {
        ListNode<T> p = first.next;
        // 遍历双链表
        while (p != last) {
            if (p.data.equals(value)) {
                // 将上一个节点的尾指针指向下一个节点
                p.pre.next = p.next;
                // 将下一节点的头指针指向上一个节点
                p.next.pre = p.pre;
                // 当前指针赋空
                p.next = null;
                p.pre = null;
                size--;
                break;
            }
            p = p.next;
        }
    }

    @Override
    public void delete(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        // 指针指向的节点的索引
        int i = 0;
        ListNode<T> p = first.next;
        while (p != last) {
            if (i == index) {
                // 将上一个节点的尾指针指向下一个节点
                p.pre.next = p.next;
                // 将下一节点的头指针指向上一个节点
                p.next.pre = p.pre;
                // 当前指针赋空
                p.next = null;
                p.pre = null;
                size--;
                break;
            }
            p = p.next;
            i++;
        }
    }

    @Override
    public void update(int index, T value) {
        if (index < 0 || index >= size) {
            return;
        }
        int i = 0;
        ListNode<T> p = first.next;
        while (p != last) {
            if (i == index) {
                p.data = value;
                break;
            }
            p = p.next;
            i++;
        }
    }

    @Override
    public boolean contains(T target) {
        ListNode<T> p = first.next;
        while (p != last) {
            if (p.data.equals(target)) {
                return true;
            }
            p = p.next;
        }
        return false;
    }

    @Override
    public T at(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        int i = 0;
        ListNode<T> p = first.next;
        while (p != last) {
            if (i == index) {
                return p.data;
            }
            p = p.next;
            i++;
        }
        return null;
    }

    @Override
    public int indexOf(T value) {
        int i = 0;
        ListNode<T> p = first.next;
        while (p != last) {
            if (p.data.equals(value)) {
                return i;
            }
            p = p.next;
            i++;
        }
        return -1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        ListNode<T> p = first.next;
        while (p != last) {
            sb.append(p.data);
            p = p.next;
            if (p != last) {
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    @Override
    public int getSize() {
        return size;
    }
}
标题：使用链式存储结构实现线性表（单链表、双链表）
作者：Yi-Xing
地址：http://47.94.239.232:10014/articles/2020/03/01/1583073649918.html
博客中若有不恰当的地方，请您一定要告诉我。前路崎岖，望我们可以互相帮助，并肩前行！
公告
  博客中若有不恰当的地方，请您一定要告诉我。前路崎岖，望我们可以互相帮助，并肩前行！   邮箱：yixing_zhang@foxmail.com
搜索文章
关于博主
Yi-Xing
166文章
11926浏览
10当前浏览
标签
待分类 MySQL LeetCode Linux JavaSE 算法 操作系统 坑 SpringBoot Redis 计算机网络 JVM 日志 其他 单片机 程序人生 JavaWeb Maven IDEA 数据结构 更多..
文章目录