链表
单向链表
单向链表中的每个节点包含一个指向下一个节点的指针。它只能从头节点开始,沿着指针方向依次遍历到链表的末尾。最后一个节点的指针指向 null,表示链表结束。
插入
删除
双向链表
双向链表中的每个节点除了指向下一个节点,还有一个指向前一个节点的指针。这样可以实现从头到尾和从尾到头的遍历。
插入
删除
循环链表
单向环形链表
插入
删除
双向环形链表
插入
删除
循环链表是一种特殊的链表,尾节点指向头节点,形成一个环状结构。 环形链表可以是单向也可以是双向的 。
单向链表、双向链表、循环链表的区别
单向链表(Singly Linked List):
- 每个节点只有一个指向下一个节点的指针。
- 只能从头节点开始沿着指针方向依次遍历到链表末尾。
- 遍历过程中不能回到前一个节点。
双向链表(Doubly Linked List):
- 每个节点有两个指针,一个指向前一个节点,一个指向后一个节点。
- 可以从头到尾或从尾到头遍历链表。
- 可以在常数时间内在已知节点的情况下进行节点的插入和删除操作。
循环链表(Circular Linked List):
- 尾节点的指针指向头节点,形成一个环状结构。
- 可以通过任何节点开始,遍历完整个链表。
- 在特定应用场景下可以简化一些操作,例如模拟循环队列。
单向链表与双向链表的增删改查
单向链表(Singly Linked List):
- 增:知道前驱节点时间复杂度为0(1),否则需要按序或按值查找前驱节点,时间复杂度为O(n)。
- 删:必须通过遍历找到前驱节点,所以 时间复杂度为O(n) 。
- 改:根据节点的位置,需要遍历找到要修改的节点,时间复杂度为O(n)。
- 查:遍历整个链表查找,平均时间复杂度为O(n)。
双向链表(Doubly Linked List):
- 增:知道前驱节点时间复杂度为0(1),否则需要按序或按值查找前驱节点,时间复杂度为O(n)。
- 删:双向链表中的每个节点都有指向前一个节点的指针(previous),这使得我们可以直接知道要删除节点的前驱节点,所以 时间复杂度为O(1) 。
- 改:根据节点的位置,需要遍历找到要修改的节点,时间复杂度为O(n)。
- 查:遍历整个链表查找,平均时间复杂度为O(n)。
链表在删除时只是删除节点,数据本身依然在内存中,不同的语言会有不同的处理方式,比如Java会有垃圾回收机制回收删除了的数据
栈(Stack)
栈是一种数据结构,数据既可以进入到栈中,又可以从栈中出去
栈是一种先进后出的数据结构 ,是一种只能在一端插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,需要读取数据的时候从栈顶开始弹出数据(最后一个入栈的数据被第一个读出去)。
我们称数据进入栈的动作为 压栈 ,数据从栈中出去的动作为 弹栈 。
Java中的栈Stack
底层继承了Vector
Stack的基本使用
- boolean empty() 判断栈是否为空
- E peek() 返回栈顶对象,不移除
- E pop() 返回栈顶对象,并移除
- E push(E item) 压入栈顶
- int search(Object o) 返回对象在栈的位置
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
for (int i = 1; i <= 5 ; i++) {
stack.push(i); //入栈
}
int search = stack.search(5); //返回该元素在栈中的位置,如果传入的不存在会返回 -1
System.out.println(search);
Integer peek = stack.peek(); //查看但不移除栈顶元素
System.out.println("栈顶元素:" + peek);
Integer pop = stack.pop(); //查看并移除栈顶元素
System.out.println("栈顶元素:" + pop);
/*
* 输出栈内全部元素和遍历栈都是按照顺序的(比如入栈顺序1,2,3,4就会输出1,2,3,4)
* */
System.out.println(stack); //输出栈内全部元素
for (Integer i : stack) { //遍历栈
System.out.println(i);
}
/*
* 出栈则是先进后出
* */
int len = stack.size();
for (int i = 0; i < len; i++) {
System.out.println(stack.pop()); //出栈
}
}
栈的应用
有效的括号
使用队列Deque模拟栈的数据结构,遇到左括号,入栈,遇到右括号,弹出栈顶,遍历完之后判断栈是否为空即可,为空就是符合的
- peek()方法: peek() 方法用于查看但不移除双端队列(Deque)的开头元素。它允许你查看如果你调用 pop() 将会被移除的元素。
- pop()方法: pop() 方法用于移除并返回双端队列的开头元素。类似于从栈中移除顶部元素。
- push()方法: push() 方法将一个元素添加到双端队列的开头。类似于将一个元素添加到栈的顶部
public static void main(String[] args) {
boolean valid = isValid("(([]){})");
System.out.println(valid);
}
/*
* 使用Deque<Character>模拟栈的数据结构,遇到左括号,入栈,遇到右括号,弹出栈顶,遍历完之后判断栈是否为空即可,为空就是符合的
* */
public static boolean isValid(String s) {
int len = s.length();
if (len % 2 == 1){
return false;
}
HashMap<Character, Character> map = new HashMap<>();
map.put('}','{');
map.put(']','[');
map.put(')','(');
/*
* peek()方法: peek() 方法用于查看但不移除双端队列(Deque)的开头元素。它允许你查看如果你调用 pop() 将会被移除的元素。
pop()方法: pop() 方法用于移除并返回双端队列的开头元素。类似于从栈中移除顶部元素。
push()方法: push() 方法将一个元素添加到双端队列的开头。类似于将一个元素添加到栈的顶部
* */
Deque<Character> list = new LinkedList<>();
for (int i = 0; i < len; i++) {
char ch = s.charAt(i);
if (map.containsKey(ch)){ //判断是否为右括号
if (list.isEmpty() || list.peek() != map.get(ch)){ //判断是否是相匹配的括号
return false;
}
//是,出栈
list.pop();
}else {
//不是,入栈
list.push(ch);
}
}
return list.isEmpty();
}
队列(Queue)
队列(Queue)是一种 先进后出 的数据结构,是一种只能在一端进行插入,另一端进行删除的特殊 线性表 ,它按照先进先出的原则存储数据,先进入的数据,在读取数据时先读取先进入的数据。
Java中的队列Queue是一个抽象类,不能被直接实例化
Queue的6个方法分类:
压入元素(添加):add()、offer()
- 相同:未超出容量,从队尾压入元素,返回压入的那个元素。
- 区别:在超出容量时,add()方法会对抛出异常,offer()返回false
弹出元素(删除):remove()、poll()
- 相同:容量大于0的时候,删除并返回队头被删除的那个元素。
- 区别:在容量为0的时候,remove()会抛出异常,poll()返回false
获取队头元素(不删除):element()、peek()
- 相同:容量大于0的时候,都返回队头元素。但是不删除。
- 区别:容量为0的时候,element()会抛出异常,peek()返回null。
可以使用多态的方式创建队列
public class queue {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>(); //多态的方式创建队列
for (int i = 1; i <= 5; i++) {
queue.add(i); //添加元素
}
Integer poll = queue.poll(); //查看并移除队列中的第一个元素
System.out.println("队列的第一个元素:" + poll);
Integer peek = queue.peek(); //查看但不移除队列中的第一个元素
System.out.println("队列的第一个元素:" + peek);
int size = queue.size(); //队列的长度
System.out.println("队列的长度:" + size);
for (Integer i : queue){ //遍历队列
System.out.println(i);
}
System.out.println("输出队列的所有值:" + queue);
}
}
评论区