数据结构（一）：数组与链表
2019-08-28 本文已影响0人
LY丶Smile
最近打算重新从基础开始学习，本文是学习过程中的笔记，如有错误请指正~
一、理论知识
数组与链表都是数据结构中最简单的线性结构，是数据存储的物理结构，很多别的数据结构都是从数组和链表衍生出来的，比如栈、队列、哈希表等
1. 数组（Array）
定义
有限个相同类型的变量组成的有序集合
存储
- 有限：数组的长度在创建时就已经确定了，所以如果操作不当很容易出现数组越界问题
- 有序：数组在内存中是顺序存储的，并且元素之间是紧密排列的，中间不会出现空余的内存块，所以数组的插入、删除都需要靠移动元素来腾出空间给新元素安家。
读取
- 数组中的每个元素都有下标（从0开始），可以按照元素的下标读取元素（随机读取），读取的效率比较高
从上面可以看出来数组的优势在于能够快速定位元素，更适合读多写少的场景
2. 链表（Linked List）
定义
在物理上非连续、非顺序的数据结构，由若干节点（node）所组成
- 每个node包括存放数据的变量data和指向下一个节点的指针next
- 第一个节点称为头节点，最后一个节点称为尾节点
存储
- 随机存储：链表的每一个节点分布在内存的不同位置，依靠next指针关联。可以很灵活有效地利用零散的碎片空间
- 理论上无限：只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要考虑扩容问题
读取
- 因为存储的随机性，所以只能根据节点next指针一个个找，从头节点开始向后一个一个节点逐一查找
从上面可以看出链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入、删除元素，用链表更适合
二、源码
- 数组长度是有限的，所以插入新元素时需要判断长度是否足够长
- 链表的插入、删除其实就是刷next指针
数组
/**
* 数组
* @author yangjunqiang
*
*/
public class MyArrayDemo {
private int[] array;
private int size;
public static void main(String[] args) {
MyArrayDemo myArrayDemo = new MyArrayDemo(10);
myArrayDemo.insert(1, 0);
myArrayDemo.insert(3, 1);
myArrayDemo.insert(5, 2);
myArrayDemo.insert(7, 3);
myArrayDemo.insert(9, 1);
myArrayDemo.printf();
}
// 初始化数组，并指定大小
public MyArrayDemo(int capacity) {
this.array = new int[capacity];
size = 0;
}
public void insert(int element, int index) {
if(index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出数组长度");
}
if(size >= array.length) {
resize();
}
// 从右到左，将元素后移一位
for(int i = size - 1; i > index; i--) {
System.out.println("i = " + i + " = " + array[i]);
array[i+1] = array[i];
}
array[index] = element;
size++;
}
/**
* 数组扩容
*/
public void resize() {
// 每次扩容，都是原数组大小的两倍
int[] newArray = new int[array.length * 2];
// 扩容的原理就是将旧数组的元素copy到新的数组里
System.arraycopy(array, 0, newArray, 0, array.length);
array = newArray;
}
public void update(int element, int index) {
if(index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出数组长度");
}
array[index] = element;
}
/**
* 移除元素
* @param index
*/
public int remove(int index) {
// 下标从0开始，所以index最大是size-1
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出数组长度");
}
int deletedElement = array[index];
// 从左到右，挨个将元素前移一位
for(int i = index; i < size -1; i++) {
array[i] = array[i+1];
}
size--;
return deletedElement;
}
public void printf() {
for(int i = 0; i < size; i++) {
System.out.println(array[i]);
}
}
}
链表
/**
* 链表
* 链表元素的定位全靠next指针
* 链表的优势在于能够灵活地插入、删除，但是查找效率低于数组
* 如果内存是无限的，那么链表也将是无限的
* @author yangjunqiang
*
*/
public class MyLinkedList {
// 头节点
private Node head;
// 尾节点
private Node last;
private int size;
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.insert(1, 0);
myLinkedList.insert(3, 1);
myLinkedList.insert(5, 2);
myLinkedList.insert(7, 3);
myLinkedList.insert(9, 4);
myLinkedList.output();
}
/**
* 查找元素
* @param index 位置
* @return
*/
public Node get(int index) {
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node temp = head;
// 链表的查找，只能挨个查找，因为链表的每个节点只保存了数据和next指针
for(int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
}
/**
* 插入元素
* @param data 数组
* @param index 要插入到的位置
*/
public void insert(int data, int index) {
if(index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
// 待插入的节点
Node insertNode = new Node(data);
// 空链表，插入后也只有一个元素
if(size == 0) {
head = insertNode;
last = insertNode;
}
// 在头部插入，将新插入的元素next指针指向原来的head节点，把新节点变为链表的head节点
else if(index == 0) {
insertNode.next = head;
head = insertNode;
}
// 在尾部插入，将原来的last的next指针指向新插入的元素，并将新元素置为last
else if(size == index) {
last.next = insertNode;
last = insertNode;
}
// 在中间插入
else {
// 获取前一个节点的信息
Node prevNode = get(index - 1);
// 插入值相当于替换了prevNode，所以next指针就是prevNode的next指针
insertNode.next = prevNode.next;
// prevNode的next指针改为insertNode
prevNode.next = insertNode;
}
size++;
}
/**
* 移除节点
* @param index
* @return
*/
public Node remove(int index) {
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出链表节点范围");
}
Node removeNode = null;
// 从头删除，将head的值置为它的下一个值就好
if(index == 0) {
removeNode = head;
head = head.next;
}
// 删除最后的元素
else if(index == size - 1) {
Node prevNode = get(index - 1);
removeNode = prevNode.next;
prevNode.next = null;
last = prevNode;
}
// 删除中间的元素
else {
// 将待删除元素的前一个元素的next指针改为待删除元素的next指针
Node prevNode = get(index - 1);
Node nextNode = prevNode.next.next;
removeNode = prevNode.next;
prevNode.next = nextNode;
}
size--;
return removeNode;
}
public void output() {
Node temp = head;
while( temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
}
定义Node
public class Node {
// 存储的数据
int data;
// 下一个节点
Node next;
public Node(int data) {
this.data = data;
}
}
三、参考
- 《漫画算法-小灰的算法之旅》
附件
思维导图-数组与链表
