线性表概述及单链表的 Java 实现
一, 线性表概述
线性表是指一组数据元素之间具有线性关系的元素序列, 它表现为: 除第一个元素没有直接前驱元素, 最后一个元素没有直接后继元素外, 其余所有元素都有且仅有一个直接前驱元素和直接后继元素.
根据存储结构的不同, 线性表可以分为顺序存储和链式存储.
1, 顺序存储
顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素.
数组就是采用顺序存储结构来存储的, 数组元素的保存和读取操作的时间复杂度都是 O(1), 而插入和删除操作的时间复杂度为 O(n), 其优缺点如下:
优点 缺点
快速存取, 时间复杂度 O(1) 插入, 删除时, 时间复杂度较高为, O(n)
无需为表示元素之间的逻辑关系而增加额外的存储空间 存储空间固定, 不易扩展, 容易造成空间的浪费
2, 链式存储
链式存储是指数据元素在内存空间中的存储地址可以是不连续的, 元素之间的逻辑关系通过其附带的指示信息来进行关联.
单链表, 双向链表, 循环链表等都是采用链式存储结构进行存储的.
对于单链表来说, 单个结点分为数据域和指针域, 指针域附带的指示信息是下一个结点的存储地址.
单链表元素的读取, 插入和删除的时间复杂度都是 O(n), 在插入和删除的操作上, 如果我们不知道所要操作结点的指针, 那么相比顺序存储结构的数组没有优势, 在知道要操作结点的指针的情况下, 对于插入或删除越频繁, 单链表的效率优势就越明显.
比如插入 10 个元素, 对于数组来说, 每插入一个元素都要移动 n-1 个结点, 每次的时间复杂度都是 O(n), 而对于单链表来说, 只需要在第一次插入时找到目标位置结点的指针, 后续插入都只需要通过移动指针来完成, 时间复杂度为 O(1).
二, 单链表的 Java 实现
1, 定义单链表的存储结构
- public class Node {
- E element;
- Node next;
- Node() {
- }
- Node(E e) {
- this.element = e;
- this.next = null;
- }
- }
一个 Node 结点包含两个属性, E element 为存储的数据, 指定为泛型; Node next 为逻辑上的下一个结点的存储地址.
2, 定义操作接口
- public interface Collection {
- void add(E e);
- void insert( E e, int index);
- void delete(int index);
- E get(int index);
- void modify( E e,int index);
- boolean isEmpty();
- int size();
- }
为集合, 列表类操作定义一个包含公有行为的接口.
3, 实现单链表
单链表的插入和删除操作可以抽象成两个步骤:
(1) 找到目标结点
通过头节点进行遍历, 直到找到目标结点;
(2) 插入或删除;
插入:
- //front 为 index - 1 结点, 即要插入位置的前一个结点
- node.next = front.next;
- front.next = node;
删除:
- //front 为 index - 1 结点, 即要删除位置的前一个结点
- node = front.next;
- front.next = node.next;
- // 释放 node 结点
- node = null;
单链表完整实现如下:
- public class LinkedList implements Collection {
- /**
- * 头指针
- */
- private Node<E> head;
- /**
- * 尾指针
- */
- private Node<E> tail;
- private int size;
- public LinkedList() {
- // 初始化时创建空的头指针和尾指针, 并指向同一个节点, 后续增加元素时, 尾指针后移, 但头指针一直不变
- head = new Node<E>();
- tail = head;
- size = 0;
- }
- @Override
- public void add(E e) {
- Node node = new Node<E>(e);
- // 设置尾指针的下一个节点为 node
- tail.next = node;
- // 设置 node 为新的尾指针
- tail = node;
- // 长度 + 1
- size++;
- }
- @Override
- public void insert(E e, int index) {
- verifyIndex(index, size);
- Node node = new Node<E>(e);
- // 先遍历找到 index-1 结点, 然后在 index-1 结点插入, 复杂度 O(n)
- int i = 0;
- //index - 1 结点
- Node front = head;
- while (i <index) {
- front = front.next;
- i++;
- }
- node.next = front.next;
- front.next = node;
- size++;
- System.out.println(this.toString());
- }
- @Override
- public void delete(int index) {
- verifyIndex(index, size - 1);
- // 找到 index-1 节点
- int i = 0;
- Node front = head;
- while (i < index) {
- front = front.next;
- i++;
- }
- Node target = front.next;
- front.next = target.next;
- target = null;
- size--;
- System.out.println(this.toString());
- }
- @Override
- public E get(int index) {
- verifyIndex(index, size - 1);
- Node node = head;
- int i = 0;
- while (i <= index) {
- node = node.next;
- i++;
- }
- return (E) node.element;
- }
- @Override
- public void modify(E e, int index) {
- verifyIndex(index, size - 1);
- Node node = head;
- int i = 0;
- while (i <= index) {
- node = node.next;
- i++;
- }
- node.element = e;
- System.out.println(this.toString());
- }
- @Override
- public boolean isEmpty() {
- return size <= 0;
- }
- @Override
- public int size() {
- return 0;
- }
- /**
- * 判断操作的索引是否合法,
- * @param index
- * @param end 右边界, 插入时允许在末尾插入, 即 end = size
- * @return
- */
- private void verifyIndex(int index, int end) {
- if (index < 0 || index> end) {
- throw new IndexOutOfBoundsException("invalid index for LinkedList:" + this.toString());
- }
- }
- @Override
- public String toString() {
- Node node = head;
- StringBuilder stringBuilder = new StringBuilder();
- while (node.next != null) {
- node = node.next;
- stringBuilder.append(node.element + " ");
- }
- return stringBuilder.toString();
- }
- }
GitHub 下载地址
来源: https://www.2cto.com/kf/201905/806577.html