1、什么是链表
链表是一种数据结构,和数组同级别。Java中我们使用的LInkedList,其实现原理为链表,而ArrayList其实现原理为数组。链表在插入和删除时优势明显。
单链表是一种线性表,实际上由节点(Node)组成,可以把单链表想象成为一列火车,而组成单链表的每个节点想象成为一节车厢。节点中存储了节点的值(data)以及指向下一个节点的指针(Next)。
2、单链表的实现(增删查改)
package LinkedList;
// 车厢类
class Node {
// 存储具体元素
int data;
// 存储下一个结点地址(钩子)
Node next;
public Node(int data) {
this.data = data;
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
// 火车
public class SingleLinkedList {
// 当前火车中车厢的个数(实际存储的元素个数)
private int size;
// 当前火车的第一个结点
private Node head;
// 在火车头部添加元素
public void addFirst(int data) {
// 要使用addFirst向火车中添加结点,要判断当前火车是否为空
// -> 一个结点都没有
// 要插入的结点就是第一个结点
if(size == 0) {
Node node = new Node(data);
head = node;
size ++;
}else {
// 当前火车已经存在结点了
Node node = new Node(data);
node.next = head;
head = node;
size ++;
}
}
public void addIndex(int index,int data) {
// 一定注意边界条件
// 判断index的合法性
if (index < 0 || index > size) {
System.err.println("add index illegal!");
return;
}
// 若index = 0;
if (index == 0) {
// 链表的头部节点插入
addFirst(data);
return;
}
// 说明此时index合法且在中间位置(包含最后节点)
// 此时需要找到待插入位置index的前驱节点
// 单链表中只能从前到后遍历
Node node = new Node(data);
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
// prev引用指向当前插入index的前驱
node.next = prev.next;
prev.next = node;
size ++;
}
public void addLast(int data) {
addIndex(size,data);
}
/**
* 查询index位置的节点数据
* @param index
* @return 节点数据
*/
public int get(int index) {
if (rangeCheck(index)) {
Node node = head;
for (int i = 0;i < index;i++) {
node = node.next;
}
// 此时node指向待查找元素的索引
int data = node.data;
return data;
}else {
System.err.println("get index illegal!");
return -1;
}
}
/**
* 修改单链表中index位置的元素
* 返回修改前的元素值
* @param index
* @param data
* @return
*/
public int set(int index,int data) {
if (rangeCheck(index)) {
// 需要找到index位置的节点
Node node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
int oldData = node.data;
node.data = data;
return oldData;
}else {
System.err.println("set index illegal!");
return -1;
}
}
private boolean rangeCheck(int index) {
if (index < 0 || index >= size) {
return false;
}
return true;
}
/**
* 判断单链表中是否包含元素data
* @param data
* @return
*/
public boolean contains(int data) {
Node node = head;
while (node != null) {
if (node.data == data) {
System.out.println("找到元素!");
return true;
}
node = node.next;
}
System.out.println("没有找到该元素");
return false;
}
public void removeFirst() {
Node node = head;
head = head.next;
node.next = null;
size --;
}
public void removeIndex(int index) {
// 判断边界条件
if (rangeCheck(index)) {
if (index == 0) {
// 此时删除头节点
removeFirst();
}else {
// 此时index删除的中间位置节点
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
// prev指向待删除节点的前驱节点
// node就是待删除的节点
Node node = prev.next;
// 链接前驱节点和后继节点
prev.next = node.next;
// 将当前节点的next引用置为空,脱钩操作
node.next = null;
size --;
}
}else {
System.err.println("remove index illegal!");
}
}
/**
* 删除链表中指定元素的第一个节点
* @param data
*/
public void removeValueOnce(int data) {
// 先要找到待删除的元素的节点
// 先判断头节点的情况
if (head.data == data) {
// 此时头节点就是第一个待删除的节点
removeFirst();
}else {
// 此时头节点一定不是要删除的节点
// 从头节点开始找到待删除的节点前驱
Node prev = head;
// 此时要看下一个节点的情况
while (prev.next != null) {
// 找到待删除的节点
if (prev.next.data == data) {
// 此时perv就是待删除节点的前驱
// node节点就是待删除的节点
Node node = prev.next;
// 将prev跳过当前node
prev.next = node.next;
node.next = null;
size --;
break;
}else {
// 此时prev的下一个节点不是待删除的节点
// 继续向下一个节点前进
prev = prev.next;
}
}
}
}
public void removeAllValue(int data) {
// 判断头节点的情况
// 头节点以及之后出现了多个连续待删除的节点
while (head != null && head.data == data) {
Node node = head;
head = head.next;
node.next = null;
size --;
}
// 此时head一定不是待删除的节点
// head.data != data
if (head == null) {
// 此时链表全部是待删除的节点,全部删除完毕
return;
}else {
// 此时头节点已经处理完毕,并且链表也不为空,向下一个节点开始判断
Node prev = head;
while (prev.next != null) {
if (prev.next.data == data) {
// node就是待删除的节点
Node node = prev.next;
prev.next = node.next;
node.next = null;
size --;
}else {
// 此时prev的下一个节点不是要删除的节点,prev继续向后走一个单位
prev = prev.next;
}
}
}
}
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addLast(2);
singleLinkedList.addLast(2);
singleLinkedList.addLast(2);
singleLinkedList.addLast(3);
singleLinkedList.addLast(2);
System.out.println(singleLinkedList);
singleLinkedList.removeAllValue(2);
// 3
System.out.println(singleLinkedList);
}
@Override
public String toString() {
String ret = "";
// 为啥此时要有一个临时变量node来存储head的值?
Node node = head;
while (node != null) {
ret += node.data + "->";
// 继续访问下一节车厢
node = node.next;
}
ret += "NULL";
return ret;
}
}
3、链表顺序表(数组)的比较
①空间资源分配
数组:数组又叫做顺序表,顺序表是在内存上开辟一段连续的空间来存储数据,数组不允许动态定义数组大大小,即只能在数组定义的时候确定数组的大小。而在实际的使用过程中,用户也无法确定数组的大小,往往出现两种情况:分配的空间太小,数组不够用;分配的空间太大,造成内存空间浪费。
链表:链表可以看成一列小火车,其由一节节车厢相连而成,物理上是不连续的,逻辑上连续,链表进行动态内存分配,可以适应数据动态的增减的情况。需要新的数据,就new一个节点出来,与原链表相连,不需要时则进行删除,空间释放,不会造成空间的浪费。
②表操作时间复杂度
数组:数组就像编了号站成一排的人,查找某个位置的人很容易,直接根据编号进行查找O(1),而若是进行删除和插入操作就很复杂,后面的人身上的编号都要发生变化O(n)。
链表:链表就像一列火车,查找某节车厢,需要从前往后遍历O(n),比较复杂,而插入和删除则只需要进行脱钩和连钩操作O(1)。