链表
数组和链表都属于线性表。线性表在计算机中有俩种存储方式,按照顺序存储的就是数组,按照链式存储的就是链表,二者最大的区别在于一个是顺序存储(地址空间连续)一个是链式存储(地址空间不连续)。因此数组元素只包含元素值就可以了,链表元素需要同时包含元素值和下一个元素的地址
内存分配方式不同:
数组是静态分配,使用前需要申请好内存,初始化好以后内存大小不能再被改变
链表是动态分配,按需申请内存,长度可动态变化
插入删除遍历方式不同:
数组:按序插入或者删除某个元素需要O(n)的复杂度遍历数组寻找元素(如果元素和数组索引刚好是一一对应关系的话那么O(1)的复杂度即可找到元素),O(n)的复杂度移动数组元素进行插入或者删除
链表:按序插入或者删除某个元素需要O(n)的复杂度遍历链表寻找元素,O(1)的复杂度插入或者删除
分析
题目要求从尾到头打印链表,我们熟知链表的遍历是从头结点开始,通过链表中每个结点存储的下一个结点的地址依 次向后访问每个元素,即使有再多种解题方法一次对链表的遍历肯定是少不了的,仔细思考遍历元素和打印元素是俩回事,可以在不同的时间段进行,遍历完一遍肯定可以拿到链表的正向序列,我们可以把它按序存储到某个有序的数据结构里面,然后再通过O(n)的方式从尾到头打印即可满足题目需求,java中ArrayList是有序的。或者换种思考方式,第一个遍历到的结点最后输出,最后一个遍历到的结点第一个输出,先入后出这是栈这个数据结构的典型特征
(代码中实现了链表最基本的增加结点,删除结点,正向遍历结点方法)
public class LinkNode {
int val;
LinkNode next;
public LinkNode(int data) {
this.val = data;
this.next = null;
}
}
import java.util.Deque;
import java.util.LinkedList;
public class LinkList {
LinkNode head;
public LinkList() {
this.head = null;
}
//添加元素
public void addNode(int data) {
LinkNode node = new LinkNode(data);
if (this.head == null) {
this.head = node;
} else {
LinkNode cur = this.head;
while(cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
//正序打印
public void print() {
LinkNode node = this.head;
while(node != null) {
System.out.print(node.val);
System.out.print(" ");
node = node.next;
}
System.out.println();
}
//倒序打印
public void reversePrint() {
Deque<Integer> stack = new LinkedList<>();
LinkNode cur = this.head;
while(cur != null) {
stack.push(cur.val);
cur = cur.next;
}
while(stack.size() > 0) {
System.out.print(stack.peek());
System.out.print(" ");
stack.pop();
}
System.out.println();
}
//删除元素
public void deleteNode(int data) {
if (this.head != null) {
LinkNode pDelete = null;
if (this.head.val == data) {
pDelete = this.head;
this.head = this.head.next;
} else {
LinkNode cur = this.head;
while(cur.next != null && cur.next.val != data) {
cur = cur.next;
}
if (cur.next != null && cur.next.val == data) {
pDelete = cur.next;
cur.next = cur.next.next;
}
}
if (pDelete != null) {
pDelete = null;
}
}
}
}
public class Five {
public static void main(String[] args) {
LinkList list = new LinkList();
list.addNode(1);
list.addNode(2);
list.addNode(3);
list.addNode(4);
//测试倒序遍历
list.reversePrint();
LinkList listOne = new LinkList();
//测试空链表倒序遍历
listOne.reversePrint();
//测试正序遍历
list.print();
//测试删除
list.deleteNode(12);
list.deleteNode(2);
list.print();
list.addNode(5);
list.print();
list.deleteNode(1);
list.print();
}
}