LinkedList容器介绍
LinkedList底层用双向链表实现的存储。特点：查询效率低，增删效率高，线程不安全。 双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两 个指针，分别指向前一个节点和后一个节点。 所以，从双向链表中 的任意一个节点开始，都可以很方便地找到所有节点。
LinkedList的存储结构图
每个节点都应该有3部分内容：
class Node<E> { Node<E> previous; //前一个节点 E element; //本节点保存的数据 Node<E> next; //后一个节点 }
List实现类的选用规则
如何选用ArrayList、LinkedList、Vector?
1 需要线程安全时，用Vector。
2 不存在线程安全问题时，并且查找较多用ArrayList（一般使用它）
3 不存在线程安全问题时，增加或删除元素较多用LinkedList
LinkedList容器的使用（List标准）
LinkedList实现了List接口，所以LinkedList是具备List的存储特征的 (有序，元素有重复)。
public class LinkedListTest { public static void main(String[] args) { //实例化LinkedList容器 List<String> list = new LinkedList<>(); //添加元素 boolean a = list.add("a"); boolean b = list.add("b"); boolean c = list.add("c"); list.add(3,"a"); System.out.println(a+"\t"+b+"\t"+c); for(int i=0;i<list.size();i++){ System.out.println(list.get(i)); } } }
LinkedList容器的使用（非List标准）
public class LinkedListTest2 { public static void main(String[] args) { System.out.println("-------LinkedList-------------"); //将指定元素插入到链表开头 LinkedList<String> linkedList1 = new LinkedList<>(); linkedList1.addFirst("a"); linkedList1.addFirst("b"); linkedList1.addFirst("c"); for (String str:linkedList1){ System.out.println(str); } System.out.println("----------------------"); //将指定元素插入到链表结尾 LinkedList<String> linkedList = new LinkedList<>(); linkedList.addLast("a"); linkedList.addLast("b"); linkedList.addLast("c"); for (String str:linkedList){ System.out.println(str); } System.out.println("---------------------------"); //返回此链表的第一个元素 System.out.println(linkedList.getFirst()); //返回此链表的最后一个元素 System.out.println(linkedList.getLast()); System.out.println("-----------------------"); //移除此链表中的第一个元素，并返回这个元素 linkedList.removeFirst(); //移除此链表中的最后一个元素，并返回这个元素 linkedList.removeLast(); for (String str:linkedList){ System.out.println(str); } System.out.println("-----------------------"); linkedList.addLast("c"); //从此链表所表示的堆栈处弹出一个元素,等效于removeFirst linkedList.pop(); for (String str:linkedList){ System.out.println(str); } System.out.println("-------------------"); //将元素推入此链表所表示的堆栈 这个等效于addFisrt(E e) linkedList.push("h"); for (String str:linkedList){ System.out.println(str); } } }
LinkedList的源码分析
添加元素
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
成员变量
transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;
添加元素
/** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */ public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
头尾添加元素
addFirst
/** * Inserts the specified element at the beginning of this list. * * @param e the element to add */ public void addFirst(E e) { linkFirst(e); } /** * Links e as first element. */ private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }
addLast
/** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #add}. * * @param e the element to add */ public void addLast(E e) { linkLast(e); } /** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
获取元素
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { checkElementIndex(index); return node(index).item; }
private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
/** * Tells if the argument is the index of an existing element. */ private boolean isElementIndex(int index) { return index >= 0 && index < size; }
/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
Set接口介绍
Set接口继承自Collection接口，Set接口中没有新增方法，它和 Collection接口保持完全一致。我们在前面学习List接口的使用方 式，在Set中仍然适用。因此，学习Set的使用将没有任何难度。
Set接口特点
Set特点：无序、不可重复。无序指Set中的元素没有索引，我们只 能遍历查找；不可重复指不允许加入重复的元素。更确切地讲，新 元素如果和Set中某个元素通过equals()方法对比为true，则只能保 留一个。
Set常用的实现类有：HashSet、TreeSet等，我们一般使用 HashSet。
HashSet容器的使用
HashSet是Set接口的实现类。是Set存储特征的具体实现。
public class HashSetTest { public static void main(String[] args) { //实例化HashSet Set<String> set = new HashSet<>(); //添加元素 set.add("a"); set.add("b1"); set.add("c2"); set.add("d"); set.add("a"); //获取元素,在Set容器中没有索引，所以没有对应的get(int index)方法 for(String str: set){ System.out.println(str); } System.out.println("--------------------"); //删除元素 boolean flag = set.remove("c2"); System.out.println(flag); for(String str: set){ System.out.println(str); } System.out.println("------------------------"); int size = set.size(); System.out.println(size); } }
HashSet存储特征分析
HashSet 是一个不保证元素的顺序且没有重复元素的集合，是线程 不安全的。HashSet允许有null 元素。
无序：
在HashSet中底层是使用HashMap存储元素的。HashMap底层使 用的是数组与链表实现元素的存储。元素在数组中存放时，并不是 有序存放的也不是随机存放的，而是对元素的哈希值进行运算决定 元素在数组中的位置。
不重复：
当两个元素的哈希值进行运算后得到相同的在数组中的位置时，会 调用元素的equals()方法判断两个元素是否相同。如果元素相同则 不会添加该元素，如果不相同则会使用单向链表保存该元素。
通过HashSet存储自定义对象
创建Users对象
public class Users { private String username; private int userage; public Users(String username, int userage) { this.username = username; this.userage = userage; } public Users() { } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Users users = (Users) o; if (userage != users.userage) return false; return username != null ? username.equals(users.username) : users.username == null; } @Override public int hashCode() { int result = username != null ? username.hashCode() : 0; result = 31 * result + userage; return result; } public String getUsername() { return username; } public void setUsername(String username) { this.username = username; } public int getUserage() { return userage; } public void setUserage(int userage) { this.userage = userage; } @Override public String toString() { return "Users{" + "username='" + username + '\'' + ", userage=" + userage + '}'; } }
在HashSet中存储Users对象
public class HashSetTest2 { public static void main(String[] args) { //实例化HashSet Set<Users> set = new HashSet<>(); Users u = new Users("oldlu",18); Users u1 = new Users("oldlu",18); set.add(u); set.add(u1); System.out.println(u.hashCode()); System.out.println(u1.hashCode()); for(Users users:set){ System.out.println(users); } } }
HashSet底层源码分析
成员变量
private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object();
添加元素
/** * Adds the specified element to this set if it is not already present. * More formally, adds the specified element <tt>e</tt> to this set if * this set contains no element <tt>e2</tt> such that * <tt>(e==null ? e2==null : e.equals(e2)) </tt>. * If this set already contains the element, the call leaves the set * unchanged and returns <tt>false</tt>. * * @param e element to be added to this set * @return <tt>true</tt> if this set did not already contain the specified * element */ public boolean add(E e) { return map.put(e, PRESENT)==null; }
TreeSet容器的使用
TreeSet实现了Set接口，它是一个可以对元素进行排序的容器。底 层实际是用TreeMap实现的，内部维持了一个简化版的TreeMap， 通过key来存储元素。 TreeSet内部需要对存储的元素进行排序，因 此，我们需要给定排序规则。
排序规则实现方式：
1、通过元素自身实现比较规则。
2、通过比较器指定比较规则。
public class TreeSetTest { public static void main(String[] args) { //实例化TreeSet Set<String> set = new TreeSet<>(); //添加元素 set.add("c"); set.add("a"); set.add("d"); set.add("b"); set.add("a"); //获取元素 for(String str :set){ System.out.println(str); } } }
