数据结构 1 线性表详解 链表、 栈 、 队列 结合JAVA 详解
程序猿小码 人气:0
## 前言
其实在学习数据结构之前,我也是从来都没了解过这门课,但是随着工作的慢慢深入,之前学习的东西实在是不够用,并且太皮毛了。太浅,只是懂得一些浅层的,我知道这个东西怎么用,但是要优化、或者是解析,就不知道该咋弄了。比如JAVA 最有名的几个容器:
- List
- Set
- MAP
- Queue
这些都是涉及到有关数据结构的,以及一些简单的算法。排序、冒泡排序、二分法这些,都要涉及到时间复杂度、以及数据结构的知识,这门课,还是很重要的。
## 为了啥
其实数据结构,结构这个词,就是将我们原本的一些数据,按照某种结构放到一起,为了更加便利以及后期对于这些数据的利用。不能胡来,乱放一遭,那样整理起来很麻烦,并且不方便以后的二次利用。
平时使用的数据,要么是基本类型、要么就是引用类型、数组、这些就是最基本的。加入需要存一个比如层级结构的岗位,那普通的数组就没有办法了。
![image.png](https://file.chaobei.xyz/blogs/image_1583466904155.png_imagess)
这里我们所涉及到的内容其实就是 数据的 `结构`
## 结构分类
数据结构的分类,到底有哪些呢,如何去理解他们,就是我们本节课的内容。这里我们将接触到线性表、树状图、图存储结构等
### 线性表
线性表其实和数组有些类似。我们都知道,所有数据的类型都可以通过
最基本的 `数组` `指针(引用类型)` 这两种最基本的类型构造。
线性表可以细分为:
- 顺序表
- 链表
- 栈
- 队列
本节课就围绕线性表,将这几种类型依次解释清楚
## 顺序表
顺序表最常见的,当然就是数组(不等同数组),满足 `一对一` 何谓一对一呢,就是其里面存储的元素,他们的类型,都是存在相同类型的关系,并且紧挨着连接起来的。例如:
```java
String [] array = new String[] {"a","b","c"};
```
类似于这种,除掉首元素和尾元素,每个元素前后都有相邻的元素。这样的我们就叫做顺序表
![image.png](https://file.chaobei.xyz/blogs/image_1583475589373.png_imagess)
JAVA 里面我们知道最基本的List 接口,下面有一个 `ArrayList`
ArrayList 底层就是以一个数组,其就是一个顺序表。
### 基本操作
我这里全部以JAVA 为例。
```java
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
```
通过这个构造函数,我们可以发现,传入一个指定的大小数,大于0,则指定基本数组的大小为传入大小。 虽然这个数组是支持自动扩容的,我们还是研究一下
### add() 增加元素到尾部
```java
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
```
`ensureCapacityInternal`是对数组的监测,若大小不足以容纳,则扩容的机制
这里的增加元素其实很简单,就将元素放到size ,也就是容器当中元素数的位置,首次放入元素的时候,size 初始化就是0 而后自增,很简单
### add() 插入元素
```java
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
```
`rangeCheckForAdd` 检查插入位置有没有超过数组大小。则直接抛出异常
扩容后,将插入点后面的元素往后移动一个位置,通过`System.arraycopy`复制方式实现
![image.png](https://file.chaobei.xyz/blogs/image_1583478124630.png_imagess)
### 查找指定下标 get()
```java
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
```
这个就不细说了,太简单了。
### remove() 移除元素
```
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = 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;
}
```
这个和上面指定位置插入一个元素刚好相反,把指定位置的元素移除掉后,后面的元素往前移动一位,而后将最后元素的位置进行清理。
### 总结
顺序表最大的特点是:查询快,因为是数组,直接下标出。插入和移除就比较慢了。因为要移动、复制数组,很麻烦
## 链表
在上面我们已经说过了,任何的数据类型都可以通过最基本的数组和指针构造。链表也不例外,相比于数组,数组则是定长的,不管存储的满否,都申请了一定大小的内存空间,而链表则不是,链表的空间是随用随申请,数据的位置相比于数组,其实不连续的,一般来说,需要在元素上指定下一个元素的指针,来达成链接关系。
![image.png](https://file.chaobei.xyz/blogs/image_1583476164210.png_imagess)
每个元素上都有一块位置用于指向下一个元素(指针)
这里我画的不连续也就是为了表示元素的不连续性
```java
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
```
链表在JAVA 当中最具代表性的就是 LinkedList(双向链表),就是每个元素会带有它的上一个节点和下一个节点的指针,我们图上画出来的是单向链表。
### add(E e)
```java
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
```
新下挂一个节点的时候,将最后一个节点(null)保存到 l 下,然后构造出一个新节点,将本节点作为最后一个最后一个节点。
![image.png](https://file.chaobei.xyz/blogs/image_1583480182481.png_imagess)
### add(int Index,E e)
```java
void linkBefore(E e, Node succ) {
// assert succ != null;
final Node pred = succ.prev;
final Node newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
```
这里两个参数,E 表示将要插入的元素,
![image.png](https://file.chaobei.xyz/blogs/image_1583481243811.png_imagess)
两边链表断开,new 一个新的节点,连接即可。
![image.png](https://file.chaobei.xyz/blogs/image_1583481330801.png_imagess)
### get(i) 查找
```java
Node node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
```
链表的查找指定下标就比较费时了。需要一个个遍历。其实是很麻烦的。
### remove(i)
```java
E unlink(Node x) {
// assert x != null;
final E element = x.item;
final Node next = x.next;
final Node prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
```
移除一个指定位置的节点,这个其实和增加一个节点时候其实是类似的。将上下节点对于这个节点的引用进行修改即可。
### 小结
链表还是比较适合于快速增加、删除、不适合于索引。因为需要全盘遍历
## 栈 Stack
堆还是按照数组为基础实现的,只不过它是一个半开的数组,怎么理解这个半开的数组呢,如图,就好像一个瓶子一样,往里面丢元素,`先进后出原则`
![image.png](https://file.chaobei.xyz/blogs/image_1583483829545.png_imagess)
### 入栈 push
将一个元素加入的栈里面,此时的元素是最外层的一个元素,此时执行出栈命令,则这个元素会被删除并返回
### 出栈 pop
删除此堆栈顶部的对象,并将该对象作为此函数的值返回。
### 查看 peek
通过 peek 查看当前栈顶的元素,只是查看,并不执行删除
## 队列 Queue
队列遵循`先进先出`原则
队列还提供额外的插入,提取和检查操作。 这些方法中的每一种都有两种形式:如果操作失败,则抛出一个异常,另一种返回一个特殊值( null或false ,具体取决于操作)。
![image.png](https://file.chaobei.xyz/blogs/image_1583485650139.png_imagess)
这里使用 `ArrayBlockingQueue` 以数组实现的阻塞队列
```java
BlockingQueue strings = new ArrayBlockingQueue(2);
```
一个有限的blocking queue由数组支持。 这个队列排列元素FIFO(先进先出)。 队列的头部是队列中最长的元素。 队列的尾部是队列中最短时间的元素。 新元素插入队列的尾部,队列检索操作获取队列头部的元素。
这是一个经典的“有界缓冲区”,其中固定大小的数组保存由生产者插入的元素并由消费者提取。 创建后,容量无法更改
### 入队 add()/offer()/put()
add 和 offer 都可以将元素加入到队列中。但是add 在超过队列容量的时候会抛出异常,offer 则会返回false
而put 操作则会在队列没有空间的时候阻塞,直到队列有空间执行
### 出队 poll()/take()
- poll检索并删除此队列的头,如果此队列为空,则返回 null 。
- take 在没有元素的时候则会阻塞
## 小结
通过本小结,我们已经学习到了最基本的线性表,而线性表又包含哪些呢
- 顺序表 ArrayList
- 链表 LinkedList
- 栈 Stack
- 队列 Queue
下一节我们将继续学习有关于字符串、数组、广义表等内容
## 参考:
http://c.biancheng.net/view/3352.html
加载全部内容