数据结构01-顺序表与链表
数据结构01-顺序表与链表
一、前言
1.什么是数据结构
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后关系，而与他们在计算机中的存储位置无关。逻辑结构包括：
- 集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
- 线性结构:数据结构中的元素存在一对一的相互关系；
- 树形结构:数据结构中的元素存在一对多的相互关系；
- 图形结构:数据结构中的元素存在多对多的相互关系。
数据的物理结构：指数据的逻辑结构在计算机存储空间的存放形式。
2.为什么要学数据结构
作为一个安卓程序员，为什么学习数据结构呢？
理由有二：
- 提高程序性能。虽然提升的不多，但是性能就是一点点提升起来的
- 进名企。去名企面试，数据结构是必问的，到时候不会就尴尬了。
二、线性表
线性表是最简单、最基本、也是最常用的一种线性结构。 线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为： (a1，a2，… ai-1，ai，ai+1，…an) ，其中n为表长， n=0 时称为空表。 它有两种存储方法：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。
顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现
三、顺序表
顺序表是顺序存储的线性表。
顺序表的应用：ArrayList。
1.ArrayList的实现
ArrayList是通过数组实现的。它的查询和修改很简单，我们看下它的增加和删除方法。
指定位置插入：
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//动态扩容：当数组元素要超出时，增加0.5倍的大小
ensureCapacityInternal(size + 1); // Increments modCount!!
//将数组中的元素从指定位置后移一位
System.arraycopy(elementData, index, elementData, index + 1,size - index);
//在指定位置插入元素
elementData[index] = element;
size++;
}
删除元素：
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//ArrayList修改的次数
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
//将数组中的元素从指定位置前移一位
System.arraycopy(elementData, index+1, elementData, index,numMoved);
//回收最后一个元素
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
2.ArrayList的优缺点
优点：
- 查改效率高：直接通过下标获取元素，直接通过下标设置元素。因为数组元素在物理上是连续的，知道其中一个的内存地址，就可以推算出其他元素的内存地址。
- 后面增删效率高：每次增加或删除，都需要移动指定位置后面的元素，所以增删的位置越靠前，需要移动的元素就越多，效率就越低；反之，效率就越高。
缺点：
- 前面增删效率低。
四、链表
链表是链式存储的线性表。包括单链表、单链循环表、双链表、双链循环表。
1.单链表
链表的逻辑关系是由节点的指针决定的，节点的指针只指向下一个节点的链表就是单链表。
单链表的应用：MessageQueue。
2.单链循环表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相连的单链表称为单循环链表，简称循环链表。
3.双链表
双链表有2个指针，next指针指向上一个节点，pre指针指向下一个节点。
双链表的应用：LinkedList。
4.双链循环表
双链循环表是闭环的双链表，它的尾节点的next指针指向头节点，它的头结点的pre指针指向尾节点。
五、单链表
1.单链表的实现
这里我们手写实现一个单链表。
查询:
private Node<E> node(int index) {
Node<E> resuleNode = null;
for (int i = 0; i <= index; i++) {
if (i == 0) {
resuleNode = first;
} else {
resuleNode = resuleNode.next;
}
}
return resuleNode;
}
指定位置添加：
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//这里可以跳过
if (index == size) {
add(e);
return;
}
//当前位置的上一个节点
Node<E> prevNode = node(index - 1);
//当前位置的节点
Node<E> nowNode = prevNode == null ? node(index) : prevNode.next;
//生成要添加的节点
Node<E> newNode = new Node<>(e, nowNode);
//改变新节点的指针
if (prevNode != null) {
prevNode.next = newNode;
} else {
first = newNode;
}
//单链表的大小
size++;
}
指定位置删除：
public void remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//当前位置的上一个节点
Node<E> prevNode = node(index - 1);
//当前位置的节点
Node<E> nowNode = prevNode == null ? node(index) : prevNode.next;;
if (prevNode == null) {
//删除首节点
removeFirst(nowNode);
} else {
//将上一个节点的指针指向下一个节点
removeNext(prevNode);
}
}
2.单链表的优缺点
优点：
- 前面查改效率高：每次查询和修改都要遍历整个链表，所以查改位置越靠前，效率越高；反之，效率越低。
- 前面增删效率高：增加和删除时，只需要改变上一个节点的指针。但是获取上一个节点，要遍历整个链表。所以增删的位置越靠前，效率越高；反之，效率越低。
缺点:
- 后面查改效率低；
- 后面增删效率低。
3.MessageQueue为什么使用单链表
MessageQueue是用来存放延迟消息的，最先发送的消息需要放在链表的最前面，每次取消息就只需要去最前面的数据。一般新插入的消息，都是放在链表的前面。所以查询和插入操作的位置都很靠前，刚好符合单链表的优点。
4.单链表的倒序
单链表由于只有首节点，所以倒序比较麻烦。这里有两种方法：
循环倒序:
public void reset() {
Node<E> curr = first;
Node<E> last = null;
while (curr != null) {
Node<E> temp = curr.next;
curr.next = last;
last = curr;
curr = temp;
}
first = last;
}
递归倒序:
public Node<E> reset(Node<E> curr) {
//结束条件
if (curr == null || curr.next == null) {
return curr;
}
//循环条件
Node<E> tail = reset(curr.next);
//循环内容
curr.next.next = curr;
curr.next = null;
return tail;
}
六、双链表
1.双链表的实现
这里我们手写实现一个双链表。
查询：
private Node<E> node(int index) {
Node<E> resuleNode = null;
if (index <= size / 2) {
for (int i = 0; i <= index; i++) {
if (i == 0) {
resuleNode = first;
} else {
resuleNode = resuleNode.next;
}
}
} else {
for (int i = size - 1; i >= index; i--) {
if (i == size - 1) {
resuleNode = last;
} else {
resuleNode = resuleNode.prev;
}
}
}
return resuleNode;
}
指定位置添加：
public boolean add(int index, E e) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
if (index == size) {
addLast(e);
return true;
}
Node<E> nowNode = node(index);
Node<E> newNode = new Node<>(e, nowNode.prev, nowNode);
nowNode.prev = newNode;
if (newNode.prev != null) {
newNode.prev.next = newNode;
} else {
first = newNode;
}
size++;
return true;
}
直接删除节点：
public boolean remove(Node<E> nowNode) {
boolean result = false;
Node<E> prevNode = nowNode.prev;
Node<E> nextNode = nowNode.next;
if (prevNode == null) {
first = nextNode;
} else {
prevNode.next = nextNode;
}
if (nextNode == null) {
last = prevNode;
} else {
nextNode.prev = prevNode;
}
size--;
return result;
}
2.双链表的优缺点
优点：
- 两端查改效率高：双链表遍历时，是从两端开始，所以查改位置越靠两端，效率越高；反之，效率越低。
- 两端增删效率高：双链表增删时，只需改变前一个节点和后一个节点的指针。但是获取上一个节点，要遍历整个链表。所以增删的位置越靠两端，效率越高；反之，效率越低。
- 直接删除节点效率：如果删除的时节点，那么就可知直接其前后节点，所以需改变前一个节点和后一个节点的指针。
缺点:
- 中间查改效率低；
- 中间增删效率低；
- 内存比单链表高:因为有2个指针。
最后
数据结构与算法专题：https://www.jianshu.com/nb/25128590
喜欢请点赞，谢谢！
