一、前言
大家好，学过数据结构的人都知道，是非常的抽象，而且很难懂，那么作为Android 程序员这个数据结构也是并不是必须要会的 但是不学还不行，所以我特意按照自己的进度来整理数据结构中非常重要的一些东西，有哪些地方不对，欢迎大家指正。
二、数据结构
定义：数据结构是计算机对内存中数据的一种安排，也可以理解成为对计算机运算的数据单元的一个抽象
研究的内容：这个可以分为逻辑结构和存储结构
逻辑结构：集合结构、线性结构、树形结构、图形结构（如下图）
线性结构
集合结构
树性结构
图形结构
存储结构：表、堆栈、队列。数组、树、二叉树、图、
三、线性表：
1、分为顺序存储结构和链式存储结构
2、首先我们看顺序表存储结构：
image
a1是a2的前驱，，ai+1是ai的后继，那么a1是没有前驱，an没有后继，n为线性表的长度，若n=0时 线性表时空
3、我们在来看顺序存储方式的特点
image
从上面我们可以看出顺序表的优点：查找贼快，尾插效率高，尾删效率也高
缺点：但是中间插入或者删除效率低，因为中间删除或者插入 后面的元素都要全部一个一个挪位置
应用场景：ArrayList
4、链式存储结构：
定义：线性表的链式存储结构的特点就是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，也可以叫做单链表
image
操作增删改查：
image
image
假如说我们要在p的后面插入节点Node e，那么我们将e.next=p.next,然后将p.next=e,这样就可以了
image
假如说我们要讲p后面的这个节点删除掉，那么只要将p.next=p,next.next;
那么单链表的优点：插入非常的快，删除效率也高，但是查找就慢了，不支持随机访问，的一个一个遍历
应用场景：MessageQueue
四、线性表（循环链表）
定义：那么什么是循环链表，上面看了单链表定义，其实循环链表就是在单链表的尾部的的指针由null指向头结点，那么这个时候就形成了一个环，这种头尾相连的单链表叫做单循环链表，
双向循环链表：就是在单循环链表上的每一个结点加上了一个前驱，指向前一个结点
我们直接看双向链表的插入：
image
上图：我们要在结点p的前面插入结点s s.pre=p.pre, p.pre.next=s.next;s.next=p,p.pre=s;
五、手写一个单链表，并且实现逆置输出
...
单向链表 实现元素的逆置
public class SingleLinkedList<E> {
记录的是链表前一个元素
Node<E> first;
int size;
单链表首先是每一个节点有一个指针 指向下一个节点的
现在实现的是单链表元素的逆置 也就是说每插入一个元素 将他的next指向前一个 第一次插入的作为尾部
public void add(E e) {
//往前一个摆放
linkFirst(e);
}
public E get(int index) {
if (index < 0 || index > size) {
return null;
}
return node(index).item;
}
private Node<E> node(int index) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
//从0-index按个往过找
node = node.next;
}
return node;
}
/**
* 添加往前一个
*
* @param e
*/
private void linkFirst(E e) {
//判断first是否为null 如果为null 则为第一个元素
Node<E> node = new Node<E>(e, first);
first = node;
size++;
}
/**
* 创建一个节点
* 只有
*
* @param <E>
*/
private static class Node<E> {
E item;
Node<E> next;
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
}
手写双链表实现
public class LinkedList<E> {
Node<E> first;
Node<E> last;
int size;
public LinkedList() {
}
public void add (E e) {
linkLast(e);
}
/**
* 在index 的位置添加一个元素
* @param index
* @param e
*/
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++;
}
}
public E get(int index) {
if(index < 0 || index >size) {
return null;
}
return node(index).item;
}
/**
* 删除index 的元素
* @param index
*/
public void remove(int index){
Node<E> target = node(index);
unlinkNode(target);
}
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 Node<E> node(int index) {
//index 处于前半部分
if (index < (size>>1)) {
Node<E> node = first;
for(int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else { //index 处于后半部分
Node<E> node = last;
for(int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
private void linkLast(E e) {
Node<E> newNode = new Node<E>(last, e, null);
Node<E> l = last;
last = newNode;
if (l == null) {
first = newNode;
}else {
l.next = newNode;
}
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;
}
}
}
网友评论