刷leetCode需要掌握的一些数据结构---JAVA篇_leetcode java常用数据结构

基本数据结构一览

1.Collection接口

Collection是最基本的集合接口，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。这个接口有两个基本方法：

public interface Collection<E>{
  boolean add(E element);
  Iterator<E> iterator();
  ...
}
1
2
3
4
5

如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用迭代子即可逐一访问Collection中每一个元素，典型的用法如下：

Iterator id=collection.iterator();
while(it.hasNext()){
  Object obj=it.next();//得到下一个元素
}
1
2
3
4

由Collection接口派生的两个接口是List和Set。

2.List接口

List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java数组。和下面要提到的Set不同，List允许有相同的元素。
实现List接口的常用类有LinkedList,ArrayList,Vector和Stack。
2.1LinkedList类
LinkedList实现了List接口，是双向链表，链表中的每个节点都包含了对前一个和后一个元素的引用。允许null元素。此外LinkedList提供额外的get,remove,insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（Stack），队列（Queue）或双向队列（Deque）。

• LinkedList 继承了 AbstractSequentialList 类。
• LinkedList 实现了 Queue 接口，可作为队列使用。
• LinkedList 实现了 List 接口，可进行列表的相关操作。
• LinkedList 实现了 Deque 接口，可作为队列使用。
• LinkedList 实现了 Cloneable 接口，可实现克隆。
• LinkedList 实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输。

2.2LinkedList基本用法
(1)添加元素：添加单个元素，如果不指定索引的话，元素将被添加到链表的最后

public static void main(String[] args){
  LinkedList<String> IList=new LinkedList<String>();
  IList.add("1");
  IList.add("2");
  IList.add("3");
}
1
2
3
4
5
6

(2)获取链表的第一个和最后一个元素

System.out.println("链表的第一个元素是："+IList.getFirst());
System.out.println("链表最后一个元素是："+IList.getLast());
1
2

(3)获取链表元素

for(String str:IList)
 System.out.println(str);
for(int size=sites.size(),i=0;i<size;i++)//size()方法用于计算链表大小
 System.out.println(IList.get(i));  
1
2
3
4

(4)删除元素

list.removeFirst();
list.removeLast();
1
2

(5)删掉所有元素：清空LinkedList

list.clear();
1

(6)删除链表特定元素

list.remove("2");//删除元素值=2的元素
list.remove(2);//删除第二个元素
1
2

(7)替换元素

list.set(3,"replaced");//使用set方法替换元素，方法的第一个参数是元素索引，后一个是替换值
1

(8)确认链表是否存在特定元素

if(list.contains("4"){
}
1
2

2.3ArrayList类
ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间，其他的方法运行时间为线性。每个ArrayList实例都有一个容量(Capacity)，用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加。使用方法和LinkedList类一致。
ArrayList类与LinkedList类的选择：
以下情况使用ArrayList:

• 频繁访问列表中的某一个元素；
• 只需要在列表末尾进行添加和删除元素操作。

以下情况使用LinkedList:

• 你需要通过循环迭代来访问列表中的某些元素；
• 需要频繁的在列表开头、中间、末尾等进行添加和删除元素操作。

2.4Vector类
Vector非常类似ArrayList，都实现了一个动态数组。但是两者是不同的，Vector是同步的。由Vector创建的Iterator，虽然和ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常；Vector包含了许多传统的方法，这些方法不属于集合框架。
Vector主要用在事先不知道数组的大小，或者只是需要一个可以改变大小的数组的情况。Vector类支持4种构造方法。
(1)第一种构造方法创建一个默认的向量，默认大小为10

Vector()
1

(2)第二种构造方法创建指定大小的向量

Vector(int size)
1

(3)第三种构造方法创建指定大小的向量，并且增量用incr指定。增量表示向量每次增加的元素数目

Vector(int size,int incr)
1

(4)第四种构造方法创建一个包含集合c元素的向量

Vector(Collection c)
1

使用方法和ArrayList一致。
2.5Stack类
Stack继承自Vector,实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当做堆栈使用。基本的push和pop方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。stack刚创建后是空栈。

3.Set接口

Set是一种不包含重复元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false,Set最多有一个null元素。很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。请注意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。
3.1HashSet
哈希表边存放的是哈希值。HashSet存储元素的顺序并不是按照存入时的顺序（和List显然不同）是按照哈希值来存的，所以取数据也是按照哈希值取得。HashSet存入不重复的规则，使用hashcode和equals。由于Set集合是不能存入重复元素的集合。那么HashSet也是具备这一特性的。HashSet如何检查重复？HashSet会通过元素的hashcode()和equals()方法进行判断是否重复。
简答一句话，如果hashCode值是不同的，那么HashSet会认为对象是不可能相等的。因此我们自定义类的时候需要重写hashCode，来确保对象具有相同的hashCode值。当hashcode()值相同，equals()返回true时，hashset集合认为这两个是相同的元素，只存储一个。
调用原理：先判断hashcode方法的值，如果相同才会去判断equals，如果不相同，是不会调用equals方法的。
使用HashSet存储自定义对象，并尝试添加重复对象（对象的重复的判定）

class Person{
private String name;
private int age;
	public int hashCode() {
		System.out.println("hashCode:" + this.name);
		return this.name.hashCode() + age * 37;
	}
 
	@Override
	public boolean equals(Object obj) {
		System.out.println(this + "---equals---" + obj);
		if (obj instanceof Person) {
			Person p = (Person) obj;
			return this.name.equals(p.name) && this.age == p.age;
		} else {
			return false;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.Map接口

请注意，Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。
4.1Hashtable
Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空的对象都可作为key或者value。添加数据使用put(key,value)，去除数据使用get(key)，这两个基本操作的时间开销为常数。简单示例如下

Hashtable numbers = new Hashtable();
numbers.put(“one”, new Integer(1));
numbers.put(“two”, new Integer(2));
numbers.put(“three”, new Integer(3));
　//　要取出一个数，比如2，用相应的key：
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
1
2
3
4
5
6
7

由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方法。ashCode和equals方法继承自根类Object，如果你用自定义的类当作key的话，要相当小心，按照散列函数的定义，如果两个对象相同，即obj1.equals(obj2)=true，则它们的hashCode必须相同，但如果两个对象不同，则它们的hashCode不一定不同。
4.1HashMap
HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null,即null value和null key。
4.2map的遍历
(1)keySet()：将map中所有的键存入到Set集合中。因为Set具备迭代器。所以可以迭代方式取出所有的键，再根据get方法，获取每一个键对应的值。keySet():迭代后只能通过get()取key。取到的结果会乱序，是因为取得数据行主键的时候，使用了HashMap.keySet()方法，而这个返回的Set记过，里面的数据是乱序排放的。

Map<String,String> map = new HashMap();
map.put("key1","lisi1");
map.put("key2","lisi2");
map.put("key3","lisi3");
map.put("key4","lisi4");  
//第一种方法，先获取map集合的所有键的set集合，keyset（）
Iterator it = map.keySet().iterator();
 //获取迭代器
while(it.hasNext()){
Object key = it.next();
System.out.println(map.get(key));
//或者第二种方法
for(String key:map.keySet())
 System.out.println(map.get(key));
1
2
3
4
5
6
7
8
9
10
11
12
13
14

(2)entrySet()：Set<Map.Entry<K,V>> entrySet() //返回此映射中包含的映射关系的 Set 视图。（一个关系就是一个键-值对），就是把(key-value)作为一个整体一对一对地存放到Set集合当中的。Map.Entry表示映射关系。entrySet()：迭代后可以e.getKey()，e.getValue()两种方法来取key和value。返回的是Entry接口。
典型用法如下：

Map map = new HashMap();
map.put("key1","lisi1");
map.put("key2","lisi2");
map.put("key3","lisi3");
map.put("key4","lisi4");
//将map集合中的映射关系取出，存入到set集合
Iterator it = map.entrySet().iterator();
while(it.hasNext()){
Entry e =(Entry) it.next();
System.out.println("键"+e.getKey () + "的值为" + e.getValue());
}
1
2
3
4
5
6
7
8
9
10
11

推荐使用第二种方式，即entrySet()方法，效率较高。