首页 > 代码库 > Java集合(一)
Java集合(一)
Data Structer 主要研究数据之间的组织关系(逻辑结构)
一:线性表结构(一对一)
---从物理区分
1:顺序存储结构(典型的数组结构ArrayList):特点:查找很快(随机访问),插入,删除很慢。前驱节点不受影响,后续节点受影响。最好的情况是 追加在最后,最坏的情况是插入第一位置,此时时间复杂度最高。
2:链式:物理上没有联系,他们的联系靠指针,形成链条。特点:无法随即访问 ,插入:
如(D插入B、C之间 ) D.next=B.next-->C,B.next-->D ,B与C才能断开
链式分单向和双向链表:双向链表更快,如java中的linkedList
3:线性结构按特殊区分:
1 栈(stack):先入后出。进栈过程称为PUSH 出栈过程称为POP
2 队列(queue):两头都是开放的,只能进不能出。加数据从队尾进,对头反之
队列中循环队列才有实用价值。
rear==front判断为空。
rear%length==front判断为满
二:树状结构(一对多的关系):二叉树
三:图形结构(多对多的关系) 定点---》边,边是有方向的 如:a-->b b-->a
四:集合(离散的结构,元素之间关系不紧密,跟索引没有关系)(大数据时代)(不用维护数据之间的关系,减少性能开销。)
散列表 java中HashTable(高效集合) 为每个元素生成一个唯一的key值,相当于索引 ,查找方式key进行比对。存的顺序与插入顺序不一致,数据是无序的。
通过哈希函数(hashCode哈希码)(对散列表的长度求余)散列存放 对表进行填充
随机访问:再做一次哈希算法 进行查找
哈希值相等 哈希冲突时:
1:(key+1)%length(散列表做大,数组动态扩展)
2:对每个元素进行追加 ,存成链表(拉链法)
Java集合(一)