Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

最基本数组和链表

家里那只橘猫 2019-01-30 11:21:00 阅读数:184 评论数:0 点赞数:0 收藏数:0

前言

​ 数组和链表是非常基本的数据结构,而数据结构就像我们常用的数据库一样,只不过我们将数据存在了运行程序的内存中,不同的数据结构就像是不同的数据库,每一个都有自己的特点,需要进行深入的了解。像我们常用的ArrayList,LinkedList就是对数组和链表的一个很好的实现。

数组简介

​ 在计算机科学中,数组数据结构,简称数组,是由相同类型的元素的集合所组成的数据结构,分配一块连续的内存来进行存储。利用元素的索引可以计算出改元素对应的存储地址。 - 来自维基百科

​ 众所周知,数组的特点就是最大的优点是查询速度快。这是因为在知道改元素的索引下,可以直接根据arr[index] 获取到该值,时间复杂度为O(1)。缺点是数组容量固定死的。那么什么场景下应该使用数组呢?数组最好应用在索引有语意的情况下。比如score[6] = 100,表示学号为6的学生分数是100分。

容量和大小

​ 什么是数组容量,什么是数组的大小。做一个比喻,家用冰箱一般是8层,每一层都是隔开来的。现在冰箱里面6层放了食材。那么8就代表数组的容量,也就是capacity,6层放了食材代表数组的大小,也就是size。在Java中数组只有一个公开的域,也就是length。代表数组的容量。

链表简介

​ 链表是一种常见的基本数据结构,是一种线性表,但是不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针。 - 来自维基百科

​ 链表是真正的动态数据结构,也是最简单的动态数据结构。优点是真正的动态,不需要处理固定容量的大小。缺点是失去了随机访问的能力。

动态数组

​ 在Java中我们可以对一个数组进行扩容,让一个数组达到一个动态的效果。其中java.util中的ArrayList就是对一个数组的动态实现。现在我通过代码实现以下动态数组。原理和ArrayList差不多。

代码如下:


/**
* @ClassName Array
* @Description 自己封装的一个动态数组
* @Author ouyangkang
* @Date 2019-01-21 09:24
**/
public class Array<E> {
//数组
private E[] data;
//数组大小
private int size;
// 容量 可以不用,为什么? 因为 他的大小就是data.length;
// private int capacity;
// 构造函数,传入数组容量capacity构造函数Array
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
// 默认参数 容量等于10
public Array() {
this(10);
}
// 获取数组大小
public int getSize() {
return size;
}
// 获取数据容量
public int getCapacity() {
return data.length;
}
// 数组大是否为空
public boolean isEmpty() {
return getSize() == 0;
}
// 添加一个元素 扩容
public void addLast(E e) {
add(size, e);
}
public void addFirst(E e) {
add(0, e);
}
// 在第index插入e
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("addLast failed : index < 0 or index > size");
}
if (size == getCapacity()) {
resize(2 * data.length);
}
// 数组插入前的元素,后移
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
// 获取index位置上的元素
public E get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Get failed . Index is illegal");
}
return data[index];
}
// 更新index位置上的元素
public void set(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Set failed . Index is illegal");
}
data[index] = e;
}
// 是否包含某个元素e
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == e){
return true;
}
}
return false;
}
// 查找改元素的位置
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return i;
}
}
return -1;
}
//移除指定index位置上的元素
public E remove(int index) {
if (index < 0 || index > size)
throw new IllegalArgumentException("remove failed . Index is illegal");
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
data[size] = null;
//缩容操作
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return ret;
}
// 移除第一个
public E removeFirst() {
return remove(0);
}
//移除最后一个
public E removeLast() {
return remove(size - 1);
}
// 移除某一个元素 有就删除 没有就不删除
public void removeElement(E e) {
int i = find(e);
if (i != -1) {
remove(i);
}
}
// 删除所有元素
public void removeAllElement(E e) {
boolean flag = true;
while (flag) {
int i = find(e);
if (i != -1) {
remove(i);
} else {
flag = false;
}
}
}
// 扩容操作 想要扩容大小
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
//全部赋值给新的数组
newData[i] = data[i];
}
data = newData;
}
public E getLast() {
return get(size - 1);
}
public E getFirst() {
return get(0);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d, capacity=%d \n", size, data.length));
res.append('[');
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1) {
res.append(", ");
}
}
res.append(']');
return res.toString();
}
}

有兴趣的可以仔细看一下,写个main方法测试一下。

链表实现

代码如下:

/**
* @ClassName LinkedList
* @Description 链表
* @Author ouyangkang
* @Date 2019-01-25 10:22
**/
public class LinkedList<E> {
// 节点类
private class Node {
public E e;
public Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
public String toString() {
return e.toString();
}
}
//利用虚拟头节点
private Node dummyHead;
private int size;
public LinkedList() {
dummyHead = new Node(null, null);
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
//在链表中添加一个元素
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("add failed Illegal index");
}
Node prv = dummyHead;
for (int i = 0; i < index; i++) {
prv = prv.next;
}
// Node node = new Node(e);
// node.next = prv.next;
// prv.next = node;
prv.next = new Node(e, prv.next);
size++;
}
//在链表头添加新元素 e
public void addFirst(E e) {
// Node node = new Node(e);
// node.next = head;
// head = node;
add(0, e);
}
// 在链表尾部
public void addLast(E e) {
add(size, e);
}
//获取链表的第index个位置的元素
// 在链表中不是一个常用操作
public E get(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("get failed Illegal index");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
public E getFirst() {
return get(0);
}
public E getLast() {
return get(size - 1);
}
// 更新
public void set(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("set failed Illegal index");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.e = e;
}
// 是否包含
public boolean contains(E e) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.e.equals(e)) {
return true;
} else {
cur = cur.next;
}
}
return false;
}
// 删除节点 返回节点值
public E remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("remove failed Illegal index");
}
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
return delNode.e;
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size - 1);
}
public String toString() {
StringBuilder res = new StringBuilder();
Node cur = dummyHead.next;
while (cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}

有兴趣的可以写一个main方法测试一下。

数组和链表的扩展

​ 我们可以根据上面写的Array类或者LinkedList类,实现一个队列,栈。只要你编写的队列,栈拥有一个Array类或者LinkedList类就可以实现了。下面我通过代码实现一下队列。队列是一种先进先出的数据结构,也就是First in First Out (FIFO)。代码如下:


/**
* @ClassName ArrayQueue
* @Description 数组实现队列
* @Author ouyangkang
* @Date 2019-01-23 17:44
**/
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array;
public ArrayQueue(){
array = new Array<>();
}
public ArrayQueue(int capacity){
array = new Array<>(capacity);
}
@Override
public void enQueue(E e) {
array.addLast(e);
}
@Override
public E deQueue() {
return array.removeFirst();
}
@Override
public E getFront() {
return array.getFirst();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue :");
res.append("front [");
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize() - 1){
res.append(", ");
}
}
res.append("] tail");
return res.toString();
}
}
/**
* @ClassName LinkListQueue
* @Description 链表实现队列
* @Author ouyangkang
* @Date 2019-01-29 09:08
**/
public class LinkListQueue<E> implements Queue<E> {
private class Node {
public E e;
public Node next;
public Node(Node next, E e) {
this.next = next;
this.e = e;
}
public Node(E e) {
this(null, e);
}
public Node() {
this(null, null);
}
public String toString(){
return e.toString();
}
}
private Node head;
private Node tail;
private int size;
@Override
public void enQueue(E e) {
if (tail == null) {
tail = new Node(e);
head = tail;
} else {
tail.next = new Node(e);
tail = tail.next;
}
size++;
}
@Override
public E deQueue() {
if (isEmpty()) {
throw new IllegalArgumentException("queue isEmpty");
}
Node ret = head;
head = head.next;
ret.next = null;
if (head == null) {
tail = null;
}
size--;
return ret.e;
}
@Override
public E getFront() {
if (isEmpty()) {
throw new IllegalArgumentException("queue isEmpty");
}
return head.e;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue: front ");
Node cur = head;
while (cur != null) {
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL tail");
return res.toString();
}
}

上面通过数组实现的队列,出队操作涉及到数组中元素的移动。时间复杂度为O(n),入队操作的时间复杂度为O(1)。链表实现的队列,入队,出队操作时间复杂度都是O(1)。但是我们可以根据数组来实现一个循环队列。这样的入队,出队操作时间复杂度都是O(1)了。有兴趣的可以实现一下。

总结

​ 数组和链表是我们非常常用的两种数据结构。也有很多数据结构是数组和链表的变形实现。总的来说,如果复杂的数据结构像一套房子的话,那么数组和链表就是砖和水泥。

版权声明
本文为[家里那只橘猫]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/Krloypower/p/10337263.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领