怎么做自己的网站平台,led灯什么网站做推广好,大连市城乡建设档案馆网站,什么是互联网营销目录
一、数据结构
1.1 数据结构概念
1.2 研究对象
1.3 常见存储结构
1.3.1 数组
1.3.2 链表
1.单向链表
2.双向链表
1.3.3 二叉树
1.3.4 栈#xff08;FILO#xff0c;先进后出#xff09;
1.3.5 队列#xff08;FIFO#xff0c;先进先出#xff09; 二、集合…目录
一、数据结构
1.1 数据结构概念
1.2 研究对象
1.3 常见存储结构
1.3.1 数组
1.3.2 链表
1.单向链表
2.双向链表
1.3.3 二叉树
1.3.4 栈FILO先进后出
1.3.5 队列FIFO先进先出 二、集合源码
2.1 List
2.1.1 ArrayList
2.1.2 Vector
2.1.3 Linkedlist
2.1.4 小结
2.2 Map
2.2.1 HashMap
2.2.2 LinkedHashMap
2.3 Set
2.4 练习 一、数据结构
1.1 数据结构概念
数据结构就是一种程序设计优化的方法论研究数据的逻辑结构和物理结构以及它们之间相互关系并对这种结构定义相应的运算目的是加快程序的执行速度、减少内存占用的空间。
1.2 研究对象
研究对象1:数据之间的逻辑关系
集合结构线性结构:一对一关系树形结构:一对多关系图形结构:多对多关系
研究对象2:数据的存储结构(或物理结构)
顺序结构链式结构索引结构散列结构
研究对象3:相关的算法操作
分配资源建立结构释放资源插入和删除获取和遍历修改和排序
在开发中习惯上如下的方式理解存储结构:
线性表(一对一关系):一维数组、单向链表、双向链表、栈、队列树(一对多关系):各种树。比如:二叉树、B树图(多对多关系)哈希表:比如:HashMap、HashSet
1.3 常见存储结构
1.3.1 数组
数组是一个容器用于存储一组相同类型的数据。数组在创建时需要指定大小并且大小在数组创建后不能更改。
大体格式
// 声明数组
int[] numbers; // 推荐的方式
int numbers[]; // 另一种方式// 初始化数组
numbers new int[5]; // 创建一个长度为5的整数数组// 也可以在声明时直接初始化
int[] numbers new int[]{1, 2, 3, 4, 5}; // 显式初始化
int[] numbers {1, 2, 3, 4, 5}; // 简化的初始化
优点
访问速度快由于数组的元素是连续存储的因此可以通过索引快速访问元素。内存利用效率高数组在内存中是连续存储的减少了内存碎片。
缺点
固定大小数组的大小在创建后不可更改可能导致空间浪费或不足。插入和删除操作复杂在数组中插入或删除元素需要移动元素效率较低。
1.3.2 链表
链表中的基本单位;Node
1.单向链表
结构
数据域存储节点的数据。指针域指向下一个节点的引用。
特点
单向性每个节点只能向后访问不能向前访问。动态大小链表的大小可以动态调整适合需要频繁插入和删除的场景。不连续存储链表的节点在内存中不必连续存储。
图示 大体格式
//创建对象
public class Test1{ Test public void test(){ Node node1 new Node(Aa); Node node2 new Node(Bb); node1.next node2; }
}
//节点类
class Node{Object date; //数据域Node next;//指针域public void setDate(Object date) {this.date date;}
}
应用场景
当需要频繁插入和删除元素时。对于元素数量不确定的场景链表比数组更合适。
2.双向链表
结构
数据域存储节点的数据。前驱指针指向前一个节点的引用。后继指针指向下一个节点的引用。
特点
双向性每个节点可以向前和向后访问操作灵活。动态大小动态调整链表的大小。占用空间多相较于单向链表节点需要更多的空间来存储前驱指针。
图示 大体格式
public class Dtest {//创建对象Testpublic void test(){DNode node1 new DNode(Aa,null,null);DNode node2 new DNode(Bb,null,node1);DNode node3 new DNode(Cc,null,node2);node1.next node2;node2.next node3;} }
class DNode {Object data; // 数据域DNode next; // 后继指针DNode prev; // 前驱指针public DNode(Object data) {this.data data;}public DNode(Object data, DNode next, DNode prev) {this.data data;this.next next;this.prev prev;}
}
应用场景
当需要频繁进行前向和后向遍历时。适用于需要双向操作的场景例如浏览器的前进和后退按钮。
1.3.3 二叉树
两个子节点被称为左子节点和右子节点。
节点
数据指向左子节点的引用指向右子节点的引用
二叉树的遍历
前序遍历根 - 左 - 右中序遍历左 - 根 - 右后序遍历左 - 右 - 根层序遍历逐层访问每一层从左到右。
大体格式
class TreeNode {TreeNode left;Object date;TreeNode right;public TreeNode(Object date) {this.date date;}public TreeNode(Object date, TreeNode left, TreeNode right) {this.date date;this.left left;this.right right;}
}// 测试
public class BinaryTreeTest {Testpublic void test1(){TreeNode treeNode new TreeNode(A,null,null);TreeNode leftNode new TreeNode(B,null,null);TreeNode rightNode new TreeNode(V,null,null);treeNode.left leftNode;treeNode.right rightNode;}
}
1.3.4 栈FILO先进后出 栈的基本概念 栈的特性 只能在栈顶进行插入和删除操作。具有栈顶和栈底两个指针栈顶指针指向最近添加的元素栈底指针指向最早添加的元素。 基本操作 push将元素压入栈顶。pop将栈顶元素弹出并返回。peek或 top查看栈顶元素但不弹出。isEmpty检查栈是否为空。size获取栈中元素的数量。
图示 使用数组实现栈
class ArrayStack {private int maxSize; // 栈的最大容量private int[] stack; // 存放栈元素的数组private int top; // 栈顶指针// 构造函数public ArrayStack(int size) {this.maxSize size;this.stack new int[maxSize];this.top -1; // 初始时栈为空}// 入栈public void push(int value) {if (top maxSize - 1) {throw new RuntimeException(栈空间已满入栈失败);}stack[top] value;}// 出栈public int pop() {if (isEmpty()) {throw new RuntimeException(栈空间已空出栈失败);}return stack[top--];}
}
使用链表实现栈
class Node {int data;Node next;public Node(int data) {this.data data;this.next null;}
}class LinkedListStack {private Node top; // 栈顶节点// 构造函数public LinkedListStack() {this.top null;}// 入栈public void push(int value) {Node newNode new Node(value);newNode.next top;top newNode;}// 出栈public int pop() {if (isEmpty()) {throw new RuntimeException(栈空间已空出栈失败);}int value top.data;top top.next;return value;}
}
1.3.5 队列FIFO先进先出
图示 代码实现
import java.util.LinkedList;
import java.util.Queue;public class QueueExample {public static void main(String[] args) {// 创建一个队列QueueInteger queue new LinkedList();// 插入元素System.out.println(入队操作);queue.offer(10);queue.offer(20);queue.offer(30);System.out.println(队列状态 queue);// 删除元素System.out.println(\n出队操作);int removedElement queue.poll(); // 从队列中删除并返回队头元素System.out.println(出队元素 removedElement);System.out.println(队列状态 queue);// 查看队头元素但不删除System.out.println(\n查看队头元素);int headElement queue.peek(); // 查看队头元素System.out.println(队头元素 headElement);System.out.println(队列状态 queue);// 遍历队列System.out.println(\n遍历队列);for (Integer element : queue) {System.out.println(element);}}
}二、集合源码
2.1 List
2.1.1 ArrayList
1.ArrayList的特点:
实现了List接口存储有序的、可以重复的数据底层使用0bject[]数组存储线程不安全的
2.ArrayList源码解析:
2.1 jdk7版本:(以jdk1.7.0_07为例) /*如下代码的执行:底层会初始化数组数组的长度为10。 0bject[]elementData new 0bject[10];*/ ArrayListString list new ArrayList(); list.add(AA); //elementData[0] AA; list.add(BB); //elementData[1] BB; 2.2 jdk8版本:(以jdk1.8.0_271内例) //如下代码的执行:底层会初始化数组即:0bject[]elementData new 0bject[]{}; ArrayListString list new ArrayList(); List.add(AA); //首次添加元素时会初始化数组elementData new 0bject[10]; elementData[0]AA List.add(BB); //elementData[1]BB; 小结
jdk1.7.0_07类似 饿汉式jdk1.8.0_271类似 懒汉式两者都是当要添加第11个元素的时候底层的elementData数组已满则需要扩容。默认扩容为原来长度的1.5倍。并将原有数组中的元素复制到新的数组中。
2.1.2 Vector
1.Vector的特点:
实现了List接口存储有序的、可以重复的数据底层使用0bject[]数组存储线程安全的
2.Vector源码解析:(以jdk1.8.0-271为例) Vector v new Vector();//底层初始化数组长度为10.0bject[]elementData new bject[10]; v.add(AA);//elementData[0] AA: v.add(BB);//elementData[1]BB; 当添加第11个元素时需要扩容。默认扩容为原来的2倍
2.1.3 Linkedlist
1.LinkedList的特点:
实现了List接口存储有序的、可以重复的数据底层使用双向链表存储线程不安全的
2.LinkedList在jdk8中的源码解析: LinkedListStringlist new LinkedList();//底层也没做啥 List,add(AA)://将AA封装到一个Node对象1中list对象的属性first、last都指向此Node对象1。 List.add(BB);//将BB封装到一个Node对象2中对象1和对象2构成一个双向链表同时last指向此Node对象2。 因为LinkedList使用的是双向链表不需要考虑扩容问题。 LinkedList内部声明:
private static class NodeE{E item;NodeE next;NodeE prel.
}
2.1.4 小结
Vector基本不使用了。ArrayList底层使用数组结构查找和添加(尾部添加)操作效率高时间复杂度为0(1)删除和插入操作效率低时间复杂度为0(n)LinkedList底层使用双向链表结构删除和插入操作效率高时间复杂度为0(1)查找和添加(尾部添加)操作效率高时间复杂度为0(n)(有可能添加操作是0(1)
在选择了ArrayList的前提下
new ArrayList():底层创建长度为10的数组。 new ArrayList(int capacity):底层创建指定capacity长度的数组。推荐大体确认数组的长度
2.2 Map
2.2.1 HashMap
1. HashMap中元素的特点
HashMap中的所有的key彼此之间是不可重复的、无序的。所有的key就构成一个Set集合。---key 所在的类要重写 hashcode()和equals()HashMap中的所有的value彼此之间是可重复的、无序的。所有的value就构成一个Collection集合。---valve 所在的类要重写 equals()HashMap中的一个 key-value ,就构成了一个 entry。HashMap中的所有的 entry 彼此之间是不可重复的、无序的。所有的entry就构成了一个Set集合。
图示 2.HashMap源码解析
2.1 jdk7中创建对象和添加数据过程(以JDK1.7.0_07为例说明): //创建对象的过程中底层会初始化数组Entry[]tablenew Entry[16]; HashMapString,Integer map new HashMap(); ... map.put(AA,78);//AA和78封装到一个Entry对象中考虑将此对象添加到table数组中。 ... 添加/修改的过程 说明
情况1:将(key1,value1)存放到数组的索引i的位置情况2,情况3:(key1,valve1)元素与现有的(key2value2)构成单向链表结构(key1,value1)指向(key2,vaue2)
注意
随着不断的添加元素在满足如下的条件的情况下考虑扩容:
(eize threshold)(null ! table[i])
当元素的个数达到临界值(-数组的长度 *加载因子)时就考虑扩容。
默认的临界值 16 *0.75 -- 12默认扩容为原来的2倍。
2.2 jdk8与jdk7 的区别 2.2.2 LinkedHashMap
1.LinkedHashMap与HashMap 的关系:
LinkedHashMap是HashMap的子类。LinkedHashMap在HashMap使用的数组单向链表红黑树的基础上又增加了一对双向链表记录添加的(keyvalue)的先后顺序。便于我们遍历所有的key-valve。
2.LinkedHashMap重写了HashMap的如下方法
NodeK,V newNode(int hash, K key, V value, NodeK,V e){LinkedHashMap.EntryK,V p new LinkedHashMap.EntrykK,V(hash, key, value, e);linkNodeLast(p);return p;
}
2.底层结构:LinkedHashMap内部定义了一个Entry
static class EntryK,V extends HashMap.NodeK,V {EntryK,V beforeafter;//增加的一对双向链表Entry(int hash, K key, v value, NodeK,V next){super(hash, key, value, next);}
}
2.3 Set
HashSet和LinkedHashSet的问题可以转换成他们”父级“的内容来回答
HashSet底层使用的是HashMapLinkedHashSet底层使用的是LinkedHashMap
2.4 练习
题目1分析此map的内存结构
public class BinaryTreeTest {public static void main(String[] args) {HashMapInteger, String map new HashMap();map.put(31, 张三);map.put(31,李四);map.put(47, 王五);map.put(45,赵六);}
}解析
