数据结构java详解_Java.数据结构.集合体系详解

I. 第一部分&＃xff1a;常见数据结构

首先简单说下数据结构.

什么是数据结构&＃xff1f;数据结构就是组织数据的方式.

常见的数据结构&＃xff1a;栈&＃xff0c;堆&＃xff0c;树&＃xff0c;图&＃xff0c;数组&＃xff0c;队列&＃xff0c;链表.

这里主要介绍与java集合体系相关的栈、数组和链表.

栈

特点&＃xff1a;压栈弹栈&＃xff0c;先进后出.

如&＃xff1a;手枪弹夹装弹过程&＃xff0c;最先压入的子弹在最下面&＃xff1b;而在射击时&＃xff0c;最先弹入枪膛的是最上面的子弹&＃xff0c;即最后压入弹夹的子弹.

队列

特点&＃xff1a;先进先出.

如&＃xff1a;子弹射出的过程&＃xff0c;先进入枪膛的子弹最先被射出.

数组

概述&＃xff1a;用来存储同一种类型元素的容器。

特点&＃xff1a;在内存中是连续的&＃xff0c;每个元素都有编号(从0开始的)&＃xff0c;方便获取。但增删就比较麻烦&＃xff0c;需要将目标位置后的所有数据前移动或后移.

查询快&＃xff0c;增删慢.

链表

概述&＃xff1a;把一些结点通过链子连接起来的数据结构。每个结点由地址域和数值域组成.

特点&＃xff1a;增删快&＃xff0c;查询慢. 增删时&＃xff0c;只需要把所插入处的前后节点链条断开&＃xff0c;增加或移除目标节点&＃xff0c;速度很快。反之&＃xff0c;查询时则需要遍历所有节点&＃xff0c;直到找到目标节点&＃xff0c;速度自然要慢。

II. 第二部分&＃xff1a;Java中的Collection(集合)体系

2.1 集合体系概览&＃xff1a;

集合体系分为4大块&＃xff1a;

Collection接口:

Collection是最基本集合接口&＃xff0c;它定义了一组允许重复的对象.

它有两个子接口&＃xff1a;List和Set.

1. List下3个实现类&＃xff1a;ArrayList, LinkedList, Vector. List是有序的。

1.1 List接口的三个儿子的特点&＃xff1a;

1.1.1 ArrayList&＃xff1a;底层数据结构是数组&＃xff0c;查询快&＃xff0c;增删慢。线程不安全(不同步)&＃xff0c;效率高。

1.1.2 Vector&＃xff1a;底层数据结构是数组&＃xff0c;查询快&＃xff0c;增删慢。线程安全&＃xff0c;效率低。

1.1.3 LinkedList&＃xff1a;底层数据结构是链表&＃xff0c;增删快&＃xff0c;查询慢。 线程不安全的&＃xff0c;效率高。

1.2 如何来选择使用哪个仔呢&＃xff1f;

keywords: 看需求!

step1: 看是否考虑安全? 安全, 则Vector.

step2: 如果不考虑安全&＃xff0c;那么是查询多还是增删多?

查询多, 则ArrayList; 增删多&＃xff0c;则LinkedList.

什么都不知道&＃xff0c;用ArrayList。

2. Set下2个实现类&＃xff1a;HashSet, TreeSet. Set是无序的。

Map接口&＃xff1a;

该接口描述了从不重复的键到值的映射。Map接口用于维护键/值对.

特征&＃xff1a;它描述了从不重复的键到值的映射.

两个重要的实现类&＃xff1a;HashMap和TreeMap.

1.HashMap&＃xff0c;中文叫散列表&＃xff0c;基于哈希表实现&＃xff0c;特点就是键值对的映射关系。一个key对应一个Value。

HashMap中元素的排列顺序是不固定的。更加适合于对元素进行插入、删除和定位。

2.TreeMap&＃xff0c;基于红黑树实现。TreeMap中的元素保持着某种固定的顺序。更加适合于对元素的顺序遍历。

Comaprable接口&＃xff1a;

Comparable可以用于比较的实现&＃xff0c;实现了Comparable接口的类可以通过实现comparaTo方法从而确定该类对象的排序方式。

Iterator接口&＃xff1a;

用于循环访问集合中的对象。

所有实现了Collection接口的容器类都有iterator方法&＃xff0c;用于返回一个实Iterator接口的对象。

Iterator对象称作迭代器&＃xff0c;Iterator接口方法能以迭代方式逐个访问集合中各个元素&＃xff0c;并可以从Collection中除去适当的元素。

2.2 Collection的接口概览(List 和 Set)

2.2.1 List接口

三个子类&＃xff1a;

ArrayList

底层数据结构是数组&＃xff0c;查询快&＃xff0c;增删慢。

线程不安全(不同步)&＃xff0c;效率高。

-Vector

底层数据结构是数组&＃xff0c;查询快&＃xff0c;增删慢。

线程安全&＃xff0c;效率低。

特有功能:

添加&＃xff1a;

void addElement(Object obj);

获取&＃xff1a;

Object elementAt(int index);

Enumeration elements(); //它返回此向量的组件的枚举,类似于迭代器Iterator

boolean hasMoreElements() //类似于hasNext()

Object nextElement(); //类似于next();

-LinkedList

底层数据结构是链表&＃xff0c;增删快&＃xff0c;查询慢。

线程不安全的&＃xff0c;效率高。

特有方法&＃xff1a;

添加&＃xff1a;

void addFirst(Object obj);//头部添加元素

void addLast(Object obj);//尾部添加元素

获取&＃xff1a;

Object getFirst();//获取头部元素

Object getLast();//获取尾部元素

删除&＃xff1a;

Object removeFirst();//移除头部元素

Object removeLast();//移除尾部元素

#问&＃xff1a;以后用List体系的那个子类&＃xff1f;

看是否考虑安全。

安全&＃xff1a;用Vector

不安全&＃xff1a;继续考虑是查询多还是增删多

查询多&＃xff1a;ArrayList

增删多&＃xff1a;LinkedList

什么都不知道&＃xff0c;用ArrayList。

#练习题&＃xff1a;

1.一个字符串集合ArrayList中含有如下元素&＃xff1a;hello, world, java, hello, .net, java, php, ios, java, android&＃xff0c;world。要求编写程序&＃xff0c;获得一个没有重复元素的新集合。

#思路&＃xff1a;

1、创建两个集合对象&＃xff0c;A&＃xff0c;B。

2、把字符串添加到集合A中。

3、遍历集合A&＃xff0c;并且判断集合B中是否包含A集合当前遍历到的元素。

4、如果包含&＃xff0c;不添加&＃xff0c;如果不包含&＃xff0c;就将该元素添加到集合B中。

5、迭代结束后&＃xff0c;集合B中存的就是去重后的元素。

练习题

#请用LinkedList来模拟栈的数据结构。

刚我们知道栈的结构为&＃xff1a;先进后出.

咱们可以使用LinkedList集合&＃xff0c;对这个类进行包装来实现先进先出的效果&＃xff0c;但不能直接使用它。

具体实现时&＃xff0c;先往集合里添加一个新数据&＃xff0c;add(); 取自己写类&＃xff0c;对LinkedList进行封装&＃xff1a;

1、需要提供添加元素的方法add() //内部封装的是&＃xff1a;addFirst()

2、需要提供获取元素的方法get(int index) //内部封装的是&＃xff1a;List体系的get(int index)方法

3、需要提供获取集合长度的方法size() //内部分装的是&＃xff1a;LinkedList的size()方法

以后遇到类似的题&＃xff0c;怎么做&＃xff1f;

解题思路&＃xff1a;

1、分析要模拟的数据结构的特点。

2、对可用的类进行包装&＃xff0c;然后提供对应的方法就可以了。

2.2 Set集合

set集合的特点: 无序,唯一

2.2.1 HashSet集合

A:底层数据结构是哈希表(是一个元素为链表的数组)

B:哈希表底层依赖两个方法&＃xff1a;hashCode()和equals()

如何保证元素唯一性?

由hashCode()和equals()保证的&＃xff0c;先调用hashCode()在调用equals().

执行顺序&＃xff1a;

首先比较哈希值是否相同:

若相同&＃xff1a;

继续执行equals()方法&＃xff1b;

-返回true&＃xff1a;元素重复了&＃xff0c;不添加&＃xff1b;

-返回false&＃xff1a;直接把元素添加到集合&＃xff1b;

若不同&＃xff1a;

就直接把元素添加到集合&＃xff1b;

2.2.2 TreeSet集合

A:底层数据结构是红黑树(是一个自平衡的二叉树)

B:保证元素的排序方式

排序方法&＃xff1a;

a:自然排序(元素具备比较性)&＃xff1a;让元素所属的类实现Comparable接口.

b:比较器排序(集合具备比较性)&＃xff1a;让集合构造方法接收Comparator的实现类对象

2.3 Map接口概览

Map也是接口&＃xff0c;但没有继承Collection接口。该接口描述了从不重复的键到值的映射。Map接口用于维护键/值对(key/value pairs)。

特征&＃xff1a;它描述了从不重复的键到值的映射。

两个重要的实现类&＃xff1a;HashMap和TreeMap

1.HashMap&＃xff0c;中文叫散列表&＃xff0c;基于哈希表实现&＃xff0c;特点就是键值对的映射关系。一个key对应一个Value。HashMap中元素的排列顺序是不固定的。更加适合于对元素进行插入、删除和定位。

2.TreeMap&＃xff0c;基于红黑书实现。TreeMap中的元素保持着某种固定的顺序。更加适合于对元素的顺序遍历。

总结

|-List

有序,可重复

|--ArrayList

底层数据结构是数组&＃xff0c;查询快&＃xff0c;增删慢.

线程不安全&＃xff0c;效率高.

|--Vector

底层数据结构是数组&＃xff0c;查询快&＃xff0c;增删慢.

线程安全&＃xff0c;效率低.

|--LinkedList

底层数据结构是链表&＃xff0c;查询慢&＃xff0c;增删快.

线程不安全&＃xff0c;效率高.

|-Set

无序,唯一

|--HashSet

底层数据结构是哈希表.

保证元素唯一性: 依赖两个方法&＃xff1a;hashCode()和equals().

|--LinkedHashSet

底层数据结构是链表和哈希表

由链表保证元素有序

由哈希表保证元素唯一

|--TreeSet

底层数据结构是红黑树。

如何保证元素排序? 自然排序; 比较器排序.

如何保证元素唯一性的呢? 根据比较的返回值是否是0来决定.

4:针对Collection集合我们到底使用谁?

唯一么? 是&＃xff1a;Set; 否&＃xff1a;List.

若用Set&＃xff1a; 排序么? 是&＃xff1a;TreeSet; 否&＃xff1a;HashSet. 如果知道是Set&＃xff0c;但是不知道是哪个Set&＃xff0c;就用HashSet. 要安全吗?是&＃xff1a;Vector; 否&＃xff1a;ArrayList或者LinkedList.

若用List: 查询多&＃xff1a;ArrayList 增删多&＃xff1a;LinkedList 如果你知道是List&＃xff0c;但是不知道是哪个List&＃xff0c;就用ArrayList.

如果你知道是Collection集合&＃xff0c;但是不知道使用谁&＃xff0c;就用ArrayList。

如果你知道用集合&＃xff0c;就用ArrayList。

5:在集合中常见的数据结构(掌握)

ArrayXxx:底层数据结构是数组&＃xff0c;查询快&＃xff0c;增删慢&＃xff1b; LinkedXxx:底层数据结构是链表&＃xff0c;查询慢&＃xff0c;增删快&＃xff1b; HashXxx:底层数据结构是哈希表。依赖两个方法&＃xff1a;hashCode()和equals()&＃xff1b; TreeXxx:底层数据结构是二叉树。两种方式排序&＃xff1a;自然排序和比较器排序&＃xff1b;