数据结构与算法(三):单向链表

数据结构与算法 2020-03-08 80 次浏览 本文字数:5554字

本文主要内容:单向链表

单向链表

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

单向链表的接口设计

  1. 创建LinkedList类,用来管理链表数据,其中size属性用来记录存储数据的数量,first属性用来指向链表的第0个元素

  2. 创建私有类Node,其中element属性用来存储元素,next属性用来指向链表中的下一个节点

  3. 按照Java接口的设计思想,定义一些方法(即对数组的增删改查操作)

       单向链表结构

单向链表的实现

private int size;       //用来记录链表长度
private Node<E> first;  //用来记录初始数据
private static final int ELEMENT_NOT_FOUND = -1;  //查找元素使用

//私有类,用来记录链表中的节点
private static class Node<E> {
    E element;          //Node类中属性1:用来记录数据
    Node<E> next;       //Node类中属性2:用来记录指针指向

    //构造方法
    public Node(E element, Node<E> next) {
        this.element = element;
        this.next = next;
    }
}

/**
 * 一、添加功能
 * 添加一条数据时,需要创建一个新的Node节点用来存放数据,然后size加1
 * 需要区分first是否有数据引用(指向)
 * @param element 添加的元素
 */
public void add(E element) {
    //当first等于null时,说明此时没用节点,所以first指向新节点
    if (first == null) {
        first = new Node<E>(element, null);
    }else {
        //当first不等于,说明链表中有节点,此时获取最后一个节点,并讲该节点的next指向新节点
        Node<E> node = node(size - 1);
        node.next = new Node<E>(element, null);
    }
    size++;
}

/**
 * 二、获取指定索引位置的元素
 * 获取index索引位置的元素
 * 注意:通过指针方式获取元素的思想
 * @param index 指定索引
 * @return 返回Node对象
 */
public Node<E> node(int index) {
    //判断索引是否越界
    rangeCheck(index);

    Node<E> node = first;
    //获取元素
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

private void outOfBounds(int index){
    throw new IndexOutOfBoundsException("索引越界");
}

private void rangeCheck(int index){
    if (index < 0 || index >= size) {
        outOfBounds(index);
    }
}
private void rangeCheckForAdd(int index){
    if (index < 0 || index > size) {
        outOfBounds(index);
    }
}

/**
 * 三、向指定索引位置插入元素
 * 插入链表,首先需要创建新节点,然后通过变更插入位置前一个元素next指针指向,插入指定位置即可
 * 需要区分插入到0的位置,使用first指向新节点和插入到非0位置,找到前一个节点进行处理两种情况
 */
public void add(int index, E element) {
    //检查索引是否越界
    rangeCheckForAdd(index);                 //因为这里要判断边界为情况,所以index可以等于size

    //插入到0位置
    if (index == 0) {
        //讲first指向新节点,新节点的next指向first指向的节点
        first = new Node<E>(element, first.next);
    }else {
        //找到指定位置前面的节点,用前面的节点next指向新节点,新节点的next指向先前节点的指向节点
        Node<E> prev = node(index - 1);
        prev.next = new Node<E>(element, prev.next);
    }
}

/**
 * 四、删除指定索引位置的元素
 * 删除元素,需要找到先前一个节点,使用前一个节点的next直接指向要删除元素的下一个节点
 * 需要区分删除0位置:只需让first指向first.next即可和其它位置
 */
public E remove(int index) {
    //检查索引是否越界
    rangeCheck(index);

    //记录要删除的节点,准备返回
    Node<E> old = first;

    if (index == 0) {
        first = first.next;
    } else {
        //找到前一个元素
        Node<E> node = node(index - 1);
        //记录需要删除的元素
        old = node.next;
        //讲前一个元素节点的next指向要删除节点的后一个节点
        node.next = node.next.next;
    }
    //注意size要减-1
    size--;
    return old.element;
}

/**
 * 五、清空元素
 * 清空元素只需讲first指向null,同时size设为0即可
 */
public void clear() {
    first = null;
    size = 0;
}

/**
 * 六、删除元素
 * 修改元素,只需将索引位置的node元素的element用新element覆盖即可
 * @return 返回旧元素的element值
 */
public E set(int index, E element) {
    //判断越界,但node()方法中已经判断
    //找到旧元素
    Node<E> node = node(index);
    //记录旧元素的element值
    E e = node.element;
    //讲就元素的element值进行覆盖
    node.element = element;
    //返回旧元素element
    return e;
}

/**
 * 七、获取指定位置的元素
 * @return 返回元素
 */
public E get(int index) {
    return node(index).element;
}

/**
 * 八、查找元素索引
 */
public int indexOf(E element) {
    //取出头节点,方便遍历
    Node<E> node = first;
    if (element == 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;
        }
    }
    return ELEMENT_NOT_FOUND;
}

/**
 * 九、获取链表元素个数
 */
public int size() {
    return size;
}

/**
 * 十、判断链表是否为空
 */
public boolean isEmpty() {
    return size == 0;
}

/**
 * 十一、判断元素是否存在
 */
public boolean contains(E element) {
    return indexOf(element) != ELEMENT_NOT_FOUND;
}

/**
 * 十二、重写toString()方法,优化打印功能
 * @return 返回
 */
public String toString() {
    StringBuilder string = new StringBuilder();
    string.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();
 }
}

本文由 WarlockMarten 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。