【Java】基础_15_堆栈和队列，数组和链表，红黑树，List子接口/ArrayList/LinkedList，set子接口，练习题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【Java】基础_15_堆栈和队列，数组和链表，红黑树，List子接口/ArrayList/LinkedList，set子接口，练习题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含10889字，纯文字阅读大概需要16分钟。
内容图文
文章目录
1.堆栈和队列
数据结构：计算机组织管理数据的方式。堆栈指的是内存图中的栈，不是堆。
2.数组和链表
梅地址+3找到菊
查询慢：知道张三在哪，不能马上知道王五在哪，挨个查。如下增删虽然不用整个动（如删除李四，只需要将箭头指向王五就行），但是还是要先查找到再删除，效率还是慢。但是直接删除张三或马六头尾元素快。
3.红黑树
二叉树：每个节点最多两个子节点。平衡树：左右尽量相等（一边的节点层次不会超过另一边的两倍）。查找树：左小右大（二分法）。二平查：红黑树（数组和链表折中方案）。
二叉搜索树BST（二查）：插入或查询一节点时，树的每一行只需要和这一行的一个节点比较（因为左小右大），复杂度完全依赖树的深度。树的行数即高度=logn【n为节点总数】【2的树行数次方为n】，BST读和写的复杂度都为logn。
有序数组查找时用二分查找法，时间复杂度logn。有序数组查询最差情况logn，而当BST为单边时（最差情况），BST查询和插入都为o(n)。
问题：为什么很多情况下用BST，而不是有序数组二分查找？因为有序数组查找用二分查找logn，但是插入要移动，插入时间复杂度为o(n)。
为什么BST很少在语言内部数据结构存储里用（因为瘦高或下面直线情况），自平衡二叉树AVL(二平)是BST（二查）的继承优化：左子树和右子树都是平衡二叉树，而且左子树和右子树深度之差绝对值不会超过1(左旋和右旋)，AVL 读和写的复杂度最差情况都为O(logn)。
AVL平衡左右子树相差1，这个条件很苛刻，导致很多情况下都不满足这个平衡条件，需要变换，变换的话需要浪费时间。红黑树（二平查）平衡条件更加宽松些左右深度差一倍【如下节点数相同是上界，节点数差一倍是下界（因为红节点子节点必须为黑）】，这样宽松条件导致我们在插入节点时候变化更少的，所以红黑树写的性能会高一些。
红黑树整体复杂度也是O（logn），树的搜索或插入复杂度完全依赖于树的深度，为什么深度差一倍还是O（logn）？如下3是3层，右边红黑树。
如下是红黑树的插入变色流程，最上面根节点必须为黑，插入节点为红节点（看插入节点的父节点和父节点的兄弟节点即叔节点）。
4.List子接口
如下是集合的框架图
package com.itheima01.list;
import java.util.ArrayList;
import java.util.List;
/*
Collection子接口：List
1. List的特点：顺引重
1. 有先后顺序：元素存储的顺序和取出的顺序相同
2. 具有整数索引,就是下标
3. 允许重复元素
2. List的方法（带索引）（List特有的，共有的在Collection讲过）
1. add(int index, E element) ：往索引位置添加一个元素
1. Java中的 三个越界异常
1. IndexOutOfBoundsException 集合
2. ArrayIndexOutOfBoundsException 数组
3. StringIndexOutOfBoundsException 字符串越界
2. get(int index)：获取指定索引的元素
3. remove(int index):移除指定索引的元素
4. set(int index, E element) ：修改指定索引的元素值
*/
public class ListDemo {
public static void main(String[] args) {
// add();
List<String> list = new ArrayList<>();
list.add("周楠");
list.add("王凤枝");
list.add("王凯");
String s = list.get(2);
System.out.println(s);
list.remove(2);
System.out.println(list);
list.set(1,"昌老师");
System.out.println(list);
}
private static void add() {
List<String> list = new ArrayList<>();
list.add("周楠");
list.add("王凤枝");
list.add("王凯");
/*
add(int index, element)
往指定索引位添加元素
index = list.size()
IndexOutOfBoundsException: : 索引越界异常
*/
list.add(3,"田锁"); //不越界，4越界
System.out.println(list);
String[] array = {};
//System.out.println(array[0]); //ArrayIndexOutOfBoundsException : 数组索引越界
String str = "abc"; // 字符串底层也是数组
// char c = str.charAt(3);
// System.out.println(c); //StringIndexOutOfBoundsException：字符串索引越界
}
}
5.ArrayList的扩容原理
Stringbuild默认length=16，扩容2倍。ArrayList底层是存Object数组，新建一个长度为原来1.5倍新数组（空）。
如下10进制的4就是2进制的0100（8421），ArrayList.java源码中出现左右移。
package com.itheima01.list;
import java.util.ArrayList;
/*
* ArrayList: 数组
* 1. 最常用: 适合 查询需求比较多的场景
* 2. 原理: ArrayList扩容原理
* ArrayList底层是数组,数组长度不可变,为什么ArrayList又可变呢? 因为数据迁移
*/
public class ArrayListDemo {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("xx");
System.out.println(3 >> 1); // 1 //除2取整
System.out.println(4 >> 1); // 2
System.out.println(10 >> 1); // 5
System.out.println(3 << 2); //12 //3*2*2，左移2位
}
}
6.LinkedList
package com.itheima01.list;
import java.util.LinkedList;
/*
LinkedList特点
1. 底层数据结构: 双向链表
2. 查询速度慢,增删快（增删需求多而且增删首尾用LinkedList）
3. 特有方法（不能使用多态，父类不能调子类特有方法）
1. addFirst 元素添加在链表开头
2. addLast（add相同） 元素添加在链表结尾
3. getFirst 获取链表开头
4. getLast 获取链表结尾
5. removeFirst 移除并返回链表开头
6. removeLast 移除并返回链表结尾
//下面两个不需要掌握
7. pop 从此列表所表示的堆栈处弹出一个元素（最顶部元素弹出,removeFirst）
8. push 将元素推入此列表所表示的堆栈（元素存储到集合顶部,addFirst）
*/
public class LinkedListDemo {
public static void main(String[] args) {
// method01();
LinkedList<String> list = new LinkedList<>();
list.add("张三"); // 是链表，不是按堆栈结构添加元素
list.add("李四");
list.add("王五");
// 链表 -> 堆栈 ，张三在栈顶
// String pop = list.pop(); // 弹栈: 栈顶元素()
// String removeFirst = list.removeFirst();//效果同上
// System.out.println(pop);
list.push("王二"); //栈顶添加，效果等同于add
System.out.println(list);
}
private static void method01() {
LinkedList<String> list = new LinkedList<>();
list.add("张三");
list.add("李四");
list.add("王五");
list.addFirst("王二");
list.addLast("马六");
System.out.println(list);
String first = list.getFirst();
String last = list.getLast();
System.out.println(first + "," + last);
System.out.println(list);
list.removeFirst();
list.removeLast();
System.out.println(list);
}
}
7.set子接口
package com.itheima02.set;
import java.util.HashSet;
import java.util.Set;
public class SetDemo {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add("张三");
set.add("李四");
boolean result = set.add("王五");
System.out.println(result);//true
boolean result2 = set.add("王五");
System.out.println(result2);//false
System.out.println(set);//[李四，张三，王五] //存取不保证顺序
}
}
8.练习题
package com.atguigu.homewok.test06;
/*
* 实例初始化的过程：
* （1）父类的实例初始化
* <init>(){
* x = 10;//父类的x
* this.print();//子类的print，因为this代表的是正在创建的子类对象，而子类重写了print，所以是子类的print
* System.out.println("Son.x = " + x);//子类的x 没有赋值x=0
x = 20;//父类的x
* }
*
* （2）子类的实例初始化
* <init>(){
* x = 30;//子类的x
* this.print();//子类的print
* System.out.println("Son.x = " + x);//子类的x 已经赋值x=30
x = 40;//子类的x
* }
*/
public class Test06 {
public static void main(String[] args) {
Father f = new Son(); //先父类构造再子类构造
System.out.println(f.x);//编译时是Father类型，访问Father中的x x=20
}
}
class Father{
int x = 10;
public Father(){
this.print();
x = 20;
}
public void print(){
System.out.println("Father.x = " + x);
}
}
class Son extends Father{
int x = 30;
public Son(){
this.print();
x = 40;
}
public void print(){
System.out.println("Son.x = " + x);
}
}
package com.atguigu.homewok.test07;
/*
*（1）类的初始化
* <clinit>(){
* int x = 5;//局部变量
x--;//局部变量 x=4
* Test07.x--;//静态变量 x = -1
* }
*
*（2）执行main方法
* System.out.println("x=" + x);//静态变量 -1
* z--;//静态变量 z=-1
* method();
* y = z++ + ++z;//静态变量 ，加载为准
* 《1》先加载z的值“-1” //《2》z自增，z=0 《3》z自增 z =1《4》加载z的值“1” 《5》求和 “-1” + “1” = 0《6》把0赋值给y y=0
* System.out.println("result:" + (z + y + ++z));
* 《1》加载z的值“1” 《2》加载y的值"0" 《3》z自增 z=2 《4》加载z的值“2” 《5》求和 “1” + “0” + “2”
*/
public class Test07 {
static int x, y, z;//类变量，静态变量，成员变量 默认值0
static {
int x = 5;//局部变量
x--;//局部变量
}
static {
x--;//静态变量
}
public static void main(String[] args) {
System.out.println("x=" + x);//静态变量
z--;//静态变量
method();
System.out.println("result:" + (z + y + ++z));//静态变量
}
public static void method() {
y = z++ + ++z;//静态变量
}
}
package com.atguigu.homewok.test08;
/*
* 1、Base b1 = new Base();
* 父类的实例初始化，和子类无关
* <init>(){
* method(100);
* System.out.println("base : " + i); base:100
* }
*
* 2、Base b2 = new Sub();
*（1） 父类的实例初始化
* <init>(){
* method(100);//执行了子类重写的method() //重要！！！
* System.out.println("sub : " + j); sub:100
* }
*（2）子类的实例初始化
* <init>(){
* super.method(70);
* System.out.println("base : " + i); base:70
* }
*/
public class Test08 {
public static void main(String[] args) {
Base b1 = new Base();
Base b2 = new Sub();
}
}
class Base {
Base() {
method(100);
}
public void method(int i) {
System.out.println("base : " + i);
}
}
class Sub extends Base {
Sub() {
super.method(70);
}
public void method(int j) {
System.out.println("sub : " + j);
}
}
package com.atguigu.homewok.test09;
// 考了两个内容：final，方法的参数传递机制
public class Test09 {
public static void main(String[] args) {
Other o = new Other();
new Test09().addOne(o); //i=1
System.out.println(o.i); //1
}
//o是引用数据类型，实参给形参的是地址值，那么形参修改了属性，实参也会修改
//o变量的值不能修改，不是说i的值不能修改
public void addOne(final Other o){
o.i++;
}
}
class Other{
public int i;//默认值0
}
package com.atguigu.homewok.test02.day10;
/*
* 实例初始化的过程：
* (1)父类的实例初始化
* <init>(){
* System.out.print("1");
* }
*
* (2)子类的实例初始化
* <init>(String name){
* System.out.print("3");
* father = new People(name + " F");//创建了一个父类的对象
* 调用父类的<init>(String name){
* System.out.print("2");
* }
* }
*/
public class Test02 {
public static void main(String[] args) {
new Child("mike");
}
}
class People {
private String name;
public People() {
System.out.print("1");
}
public People(String name) {
System.out.print("2");
this.name = name;
}
}
class Child extends People {
People father;
public Child(String name) {
//隐含了super()，走了父类的无参构造
System.out.print("3");
father = new People(name + " F");
}
public Child() {
System.out.print("4");
}
}
package com.atguigu.homewok.test07.day10;
/*
* new A(new B());
* （1）new B()
* <init>(){
* System.out.println("B");
* }
*
*（2）new A(B的对象即B b)
* <init>(B b){
* this();
* System.out.println("A");
* System.out.println("AB");
* }
*/
public class Test07 {
public static void main(String[] args) {
new A(new B());
}
}
class A {
public A() {
System.out.println("A");
}
public A(B b) {
this();
System.out.println("AB");
}
}
class B {
public B() {
System.out.println("B");
}
}
package com.atguigu.homewok.test08.day10;
/*
* （1）父类的实例初始化
* <init>(){
* System.out.println("base");
* method(100); //子类重写了，执行子类的method
* System.out.println("sub : " + j); sub:100
* }
*
* （2）子类实例初始化
* <init>(){
* System.out.println("sub"); sub
* super.method(70); //父类的method
* System.out.println("base : " + i); base 70
* }
*/
public class Test08 {
public static void main(String[] args) {
Sub s = new Sub();
}
}
//111111111111111111111111111111111
class Base{
Base(){
method(100);
}
{
System.out.println("base");
}
public void method(int i){
System.out.println("base : " + i);
}
}
//1111111111111111111111111111111111
class Sub extends Base{
Sub(){
//隐含了：super()
super.method(70);
}
{
System.out.println("sub");
}
public void method(int j){
System.out.println("sub : " + j);
}
}
内容总结
以上是互联网集市为您收集整理的【Java】基础_15_堆栈和队列，数组和链表，红黑树，List子接口/ArrayList/LinkedList，set子接口，练习题全部内容，希望文章能够帮你解决【Java】基础_15_堆栈和队列，数组和链表，红黑树，List子接口/ArrayList/LinkedList，set子接口，练习题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】