链表、栈、队列

链表

单向链表

单向链表中的每个节点包含一个指向下一个节点的指针。它只能从头节点开始,沿着指针方向依次遍历到链表的末尾。最后一个节点的指针指向 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);
    }
}
end
数据结构

评论区

暂无评论