链表的简单介绍

哈希表的简单介绍：

1.哈希表在使用层面上可以理解为一种集合结构
2.如果只有Key，没有伴随数据Value，可以使用HashSet结构
3.如果既有Key，又伴随数据Value，可以使用HashMap结构
4.有无伴随数据，是HashMap和HashSet唯一区别，底层的实际结构是一回事
5.使用哈希表增(add)、删(remove)、改(put)、查(get)的操作，可以认为时间复杂度为O(1)，但是常数时间比较大
6.放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
7.放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用就是这个东西内存地址的大小

有序表的简单介绍：

1.有序表在使用层面上可以理解为一种集合结构
2.如果只有Key，没有伴随数据Value，可以使用TreeSet结构
3.如果既有Key，又伴随数据Value，可以使用TreeMap结构
4.有无伴随数据，是TreeSet和TreeMapt唯一区别，底层的实际结构是一回事
5.有序表和哈希表的区别是，有序表把Key按照顺序组织起来，而哈希表完全不组织
6.红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同
7.放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
8.放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占用就是这个东西内存地址的大小
9.不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度

有序表的固定操作

1.void put（K key，V value）：将一个（key，value）记录加入到表中，或者将key的记录更新成value
2.V get（K key）：根据给定的key，查询value并返回
3.void remove（K key）：移出key的记录
4.boolean containsKey（K key）：询问是否有关于key的记录
5.K firstKey（）：返回所有键值的排序结果中，最小的那一个
6.K lastKey（）：返回所有键值的排序结果中，最大的那一个
7.K floorKey（K key）：如果表中存入过key，返回key；否则返回所有键值的排序结果中，key的前一个
8.K ceilingKey（K key）：如果表中存入过key，返回key；否则返回所有键值的排序结果中，key的后一个
以上所有操作时间复杂度都是O(logN)，N为有序表含有的记录

单链表的节点结构

Class Node<V>{
		V value; 
		Node next;
 }
1
2
3
4

由以上结构的节点依次连接起来所形成的链叫做单链表结构

双链表的节点结构

Class Node<V>{
	V value;
	Node next;
	Node last;
}
1
2
3
4
5

由以上结构的节点依次连接起来所形成的链叫做双链表结构
单链表和双链表结构只需要给定一个头部节点head，就可以找到剩下所有的节点

面试时链表解题的方法论：

1.对于笔试，不用太在意空间复杂度，一切为了时间复杂度
2.对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
重要技巧
1.额外数据结构记录（哈希表）
2.快慢指针

相关题目

判断一个单链表是否是回文结构
将单链表按某值划分成左边小、中间相等、右边大的形式
复制含有随机指针节点的链表

两个单链表相交的一系列问题：

判断单链表是否有环（快慢指针）：

思路： 快指针一次走两步，慢指针一次走一步，当快慢指针相遇后， 快指针回到开头并一次走一步，慢指针停留在原地并一次走一步，当快慢指针再次相遇时，即为环的入口。

求两个单链表相交的第一个节点

无环时：

这里假设两个链表分别为h1，h2，最后一个节点分别为end1，end2
1.判断end1和end2 的内存地址是否一致，若一致则会相交，反之，不相交
2.若相交，长链表先走 | length1-length2 | 步，然后长短链表一起走，当相遇时，则是相交的第一个节点

有环时：

1.若一个链表有环，一个链表无环时，两个链表不可能相交
2.当两个链表都有环时：入环节点分别为loop1、loop2
2.1 不相交
当loop1继续走，直至loop1走回到原位置时，没有遇到loop2 则不相交，返回null
2.2 共用入环节点（loop1==loop2）
化成求无环链表的相交节点
2.3 入环节点不相等
当loop1继续走，若loop1走到原位置的过程中遇到loop2，返回loop1或者loop2