概念
数据结构是对在计算机内存中的数据的一种安排。
也可以理解为对计算机机运算的数据单元的一个抽象。
数据结构的分类
- 逻辑结构：集合结构，线性结构，树形结构，图形结构
- 存储结构：表，堆栈，队列，数组，树，二叉树，图
常见的数据结构
线性表
线性表有顺序存储结构和链式存储结构
顺序存储结构（顺序表）:
优点：尾部插入效率高，支持随机访问。
缺点：中间插入和删除效率低
例子：ArrayList
链式存储结构有：单链表，双链表，单循环链表，双循环链表
优点：头插，中间插，删除效率高
缺点：不支持随机访问
例子：MessageQueue
链表的添加和删除
/添加
public void add (int index, E e) {
if(index < 0 || index >size) {
return;
}
if (index == size) {
linkLast(e);
} else {
Node<E> target = node(index);
Node<E> pre = target.prev;
Node<E> newNode = new Node<E>(pre, e, target);
//不能直接这样写
// pre.next = newNode;
// pre = newNode;
if(pre == null) {
first = newNode;
} else {
pre.next = newNode;
}
pre = newNode;
size++;
}
}
//删除
private void unlinkNode(Node<E> p) {
//不能直接这样写
// p.prev.next = p.next;
// p.next.prev = p.prev;
Node<E> pre = p.prev;
Node<E> next = p.next;
//等价与删除第一个节点
if (pre == null) {
first = p.next;
} else {
pre.next = p.next;
}
//等价与删除尾节点
if (next == null) {
last = p.prev;
} else {
next.prev = p.prev;
}
size--;
}
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
