小码哥数据结构与算法(二): 链表

1,333 阅读6分钟

本篇是恋上数据结构与算法(第一季)的学习笔记, 使用JAVA语言

动态数组有个明显的缺点, 可能会造成内存空间的大量浪费
链表可以做到用多少就申请多少内存

一、链表

  • 链表是一种链式存储的线性表, 所有元素的内存地址不一定是连续的

二、链表的设计

  • 创建类LinkedList, 用来管理链表数据, 其中的size属性记录存储数据的数量, first属性引用链表的第0个元素
  • 创建私有类Node, 其中的element属性用于存储元素, next属性用于指向链表中的下一个节点

public class LinkedList<E> {
    private int size;
    private Node<E> first;
    // 私有类, 链表中的节点
    private class Node<E> {
        E element;
        Node<E> next;
        // 构造方法
        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
}

三、链表接口设计

  • 与动态数组一样, 链表也需要提供增删改查
// 元素的数量
int size(); 
// 是否为空
boolean isEmpty();
// 是否包含某个元素
boolean contains(E element); 
// 添加元素到最后面
void add(E element); 
// 返回index位置对应的元素
E get(int index); 
// 设置index位置的元素
E set(int index, E element); 
// 往index位置添加元素
void add(int index, E element); 
// 删除index位置对应的元素 
E remove(int index); 
// 查看元素的位置
int indexOf(E element); 
// 清除所有元素
void clear(); 

四、链表接口实现

1、索引越界的判断

  • 在操作链表数据时,需要防止索引越界,到时程序异常的问题
  • 当查找和删除数据时, 需要检查索引的范围是0到size-1之间,所以方法如下
private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); 
    }
}
  • 当插入数据时,因为可以将数据加到所有数据的最后,所以需要检查索引的范围是0到size之间
private void rangeCheckForSize(int index) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size); 
    }
}

2、根据索引查找指定节点

  • 因为链表中的数据都是存在节点中, 所以操作数据时需要找到对应的节点
  • 我们可以实现一个根据索引, 来查找指定节点的方法
private Node<E> node(int index) {
    rangeCheck(index);
    // 头结点,就是first指向的那个节点
    Node<E> node = first;
    // 根据索引遍历,查找对应的节点
    for (int i = 0; i < index; i++) {
    	node = node.next;
    }
    return node;
}

3、添加数据

  • 添加数据时, 需要创建一个节点存储数据, 并将该节点拼接到最后节点的后面, 然后size1
  • 两种情况
    • 第一种: 当前链表没有数据, 新节点拼接到first
    • 第二种: 当前链表有数据, 新节点拼接到最后的节点
public void add(E element) {
    // 当first等于null时, 说明此事没有节点, 所以first引用新节点
    if (first == null) {
    	first = new Node<E>(element, null);
    }else {
    	// 当fitst不等于null时, 说明链表中有节点, 此时获取最后一个节点, 并将该节点的next指向新节点
        Node<E> node = node(size - 1);
        node.next = new Node<E>(element, null);
    }
    size++;
}

4、插入元素

  • 插入链表时, 只需要创建新节点保存元素, 然后插入指定位置即可
  • 两种情况
    • 第一种: 插入到0的位置, 需要使用first指向新节点
    • 第二种: 插入到非0位置,直接找到前一个节点进行处理
public void add(int index, E element) {
    // 检查索引是否越界
    rangeCheckForSize(index);
    // 当插入到0的位置时
    if (index == 0) {
        // 将first指向新节点, 新节点的next指向first之前指向的节点
        first = new Node<E>(element, first.next);
    }else {
        // 找到指定位置前面的节点
        Node<E> prev = node(index - 1);
        // 将前面节点的next指向新节点, 新节点的next指向prev之前指向的节点
        prev.next = new Node<>(element, prev.next);
    }
    size++;
}
  • 添加元素的方法可以简写
public void add(E element) {
    // 元素添加到size位置, 即添加到最后面
    add(size, element);
}

5、删除元素

  • 删除元素, 找到指定节点前面的节点, 然后直接指向需要删除节点的下一个节点即可, 然后size1
  • 两种情况
    • 第一种: 删除第0个元素, 需要使用first指向第1个节点
    • 第二种: 删除非0索引的元素, 找到前一个节点, 然后直接指向下一个节点即可
public E remove(int index) {
    // 检查索引是否越界
    rangeCheck(index);
    // 记录需要删除的节点
    Node<E> old = first;
    // 当删除第0个元素时, 将first的next指向索引为`1`的节点即可
    if (index == 0) {
        first = first.next;
    }else {
        // 找到前一个元素
        Node<E> prev = node(index - 1);
        // 记录需要删除的节点
        old = prev.next;
        // 将prev的next指向需要删除节点的后一个节点
        prev.next = old.next;
    }
    // size-1
    size--;
    // 返回删除的元素
    return old.element;
}

6、清空元素

  • 清空元素, 直接将first指向null即可, 同时size置为0
public void clear() {
    first = null;
    size = 0;
}

7、修改元素

  • 修改元素, 找到对应节点, 直接修改元素即可
public E set(int index, E element) {
    // 找到对应节点, node方法中已经判断了索引是否越界
    Node<E> node = node(index);
    // 记录旧元素
    E old = node.element;
    // 覆盖元素
    node.element = element;
    // 返回旧元素
    return old;
}

8、查找元素

  • 查找元素, 直接找到对应的节点, 取出元素即可
public E get(int index) {
    // node方法中已经判断了索引是否越界
    return node(index).element;
}

9、查找元素索引

  • 查找指定元素的索引, 需要遍历所有节点, 找到节点对应的元素与执行元素相等即可
  • 因为元素可以是null, 所以需要分两种情况处理
private static final int ELEMENT_ON_FOUND = -1;
public int indexOf(E element) {
    // 取出头结点
    Node<E> node = first;
    // 当element为null时的处理
    if (element == null) {
        // 遍历节点, 找到存储为null的节点, 返回索引
        for (int i = 0; i < size; i++) {
            if (node.element == null) return i;
            node = node.next;
        }
    }else {
        for (int i = 0; i < size; i++) {
            // 遍历节点, 找到存储的元素与指定元素相等的节点, 返回索引
            if (element.equals(node.element)) return i;
            node = node.next;
        }
    }
    // 没有找到元素对应的节点, 返回ELEMENT_ON_FOUND
    return ELEMENT_ON_FOUND;
 }

10、获取链表存储元素的个数

  • 获取链表存储元素的个数, 就是size的值
public int size() {
    return size;
}

11、链表是否为空

  • 链表是否为空, 只需要判断size是否等于0即可
public boolean isEmpty() {
    return size == 0;
}

12、判断元素是否存在

  • 判断元素是否存在, 只需要判断元素的索引是否为ELEMENT_ON_FOUND即可
public boolean contains(E element) {
    return indexOf(element) != ELEMENT_ON_FOUND;
}

13、打印链表中存储的数据

  • 只需要重写toString方法即可
@Override
public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("size = ").append(size).append(", [");
    Node<E> node = first;
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            string.append(",");
        }
        string.append(node.element);
        node = node.next;
    }
    string.append("]");
    return string.toString();
}