Java高级重点知识点-13-数据结构、List集合、List集合的子类

文章目录

数据结构
List集合
List的子类（ArrayList集、LinkedList集）

数据结构

栈
stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。

先进后出（即，存进去的元素，要在后它后面的元素依次取出后，才能取出该元素）。

压栈：就是存元素。即，把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置。
弹栈：就是取元素。即，把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置。

队列
队列：queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。

先进先出（即，存进去的元素，要在它前面的元素依次取出后，才能取出该元素）。

数组
数组:Array,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。

优缺点：

查找元素快
增删元素慢

链表
链表:linked list,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时i动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

优缺点：

查找元素慢
增删元素快

红黑树（一种特别的二叉树）
二叉树：binary tree ,是每个结点不超过2的有序树（tree）。

红黑树的约束:

节点可以是红色的或者黑色的
根节点是黑色的
叶子节点(特指空节点)是黑色的
每个红色节点的子节点都是黑色的
任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

优缺点：

速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍

List集合

java.util.List 接口继承自 Collection 接口，是单列集合的一个重要分支

List接口中常用方法

public void add(int index, E element) : 将指定的元素，添加到该集合中的指定位置上。
public E get(int index) :返回集合中指定位置的元素。
public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。
public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

示例代码：

import java.util.ArrayList;
import java.util.List;

public class ListDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("xiaohu");
        for (String o : list) {
            System.out.println(o);
        }
        System.out.println("-------------------------");
        list.add(1,"bird");
        for (String s : list) {
            System.out.println(s);
        }
        System.out.println("-------------------------");
        System.out.println(list.get(2));
        System.out.println("-------------------------");
        list.remove(4);
        for (String s : list) {
            System.out.println(s);
        }
        System.out.println("-------------------------");
        list.set(3,"xiaohu");
        for (String s : list) {
            System.out.println(s);
        }
    }
}

在这里插入图片描述
程序开始时，我们通过多态创建了一个list对象，通过调用父类中add（）方法，添加了4个元素并且对元素进行了遍历，然后通过List接口中的 add（int index, E element） 方法，添加“bird”字符串到指定位置中，通过 get（int index） 获取索引为2的值（也就是world），然后通过 remove(int index) 移除了索引值为4的值（也就是xiaohu），再通过 set(int index, E element) 将索引值为3的值设置为xiaohu。

List的子类（ArrayList集、LinkedList集）

ArrayList集合
java.util.ArrayList 集合数据存储的结构是数组结构。元素增删慢，查找快
LinkedList集合
java.util.LinkedList 集合数据存储的结构是链表结构。方便元素添加、删除的集合。

public void addFirst(E e) :将指定元素插入此列表的开头。
public void addLast(E e) :将指定元素添加到此列表的结尾。
public E getFirst() :返回此列表的第一个元素。
public E getLast() :返回此列表的最后一个元素。
public E removeFirst() :移除并返回此列表的第一个元素。
public E removeLast() :移除并返回此列表的最后一个元素。
public E pop() :从此列表所表示的堆栈处弹出一个元素。
public void push(E e) :将元素推入此列表所表示的堆栈。
public boolean isEmpty() ：如果列表不包含元素，则返回true。

 public static void main(String[] args) {
        LinkedList<String> list = new LinkedList();
        list.add("a");
        list.add("b");
        list.add("c");
        list.addLast("d");
        System.out.println(list.getFirst());
        System.out.println("-------------------------------");
        System.out.println(list.getLast());
        System.out.println("-------------------------------");
        System.out.println(list.removeFirst());
        System.out.println("-------------------------------");
        System.out.println(list.removeLast());
        System.out.println("-------------------------------");
        for (String o : list) {
            System.out.print(o + ",");
        }
        System.out.println("\n-------------------------------");
        list.pop();
        for (String o : list) {
            System.out.print(o + ",");
        }

        list.push("e");
        System.out.println("\n-------------------------------");
        for (String o : list) {
            System.out.print(o + ",");
        }
        System.out.println("-------------------------------");
        System.out.println(list.isEmpty());
    }