一、链表结构
1.单向链表节点结构
public class Node{
public int value;
public Node next;
public Node(int data){
value=data;
}
}
2.双向链表节点结构
public class DoubleNode{
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data){
value=data;
}
}
3.单向链表与双向链表最简单的练习
3.1单向链表与双链表如何反转
//单向链表反转
public static Node reverseLinkedList(Node head){
Node pre =null;
Node next = null;
while(head !=null){
next=head.next;
head.next=pre;
pre=head;
head=next;
}
//返回新的头结点
return pre;
}
//双向链表反转
public static DoubleNode reverseDoubleList(DoubleNode head){
DoubleNode pre=null;
DoubleNode next=null;
while(head!=null){
next=head.next;
head.next=pre;
head.last=next;
pre=head;
head=next;
}
//返回头结点
return pre;
}
3.2把给定值删除
//删除一个单链表中值为num的节点
public static Node removeValue(Node head,int num){
//判断头部节点需要删多少个
//如在3-3-3-3-2-2-1链表中，删掉值为3的节点，则需要删掉4个头部节点
while(head !=null){
if(head.value !=num){
break;
}
head=head.next;
}
//head来到第一个不需要删除的位置
Node pre=head;
Node cur=head;
while(cur != null){
//注意：java中会自动释放无法找到的节点，不需要手动释放
if(cur.value == num){
pre.next =cur.next;
}else{
pre=cur;
}
cur= cur.next;
}
retuen pre;
}
二、栈和队列
1.逻辑概念
栈：数据先进后出
队列：数据先进先出
2.栈和队列的实际实现
双向链表实现
数组实现
1.使用双向链表实现栈和队列
(1)使用双向链表模拟栈与队列的进出操作
public static class DoubleEndsQueue<T>{
public Node<T> head;//头指针
public Node<T> tail;//尾指针
//如果从头部开始加节点采用以下方法
public void addFormHead(T value){
Node<T> cur=new Node<T>(value);
if(head==null){
head=cur;
tail=cur;
}else{
cur.next=head;
head.last=cur;
head=cur;
}
}
//如果从尾部开始加节点采用以下方式
public void addFromBottom(T value){
Node<T> cur =new Node<T>(value);
if(head ==null){
head=cur;
tail=cur;
}else{
cur.last=tail;
tail.next=cur;
tail=cur;
}
}
//从头部弹出节点
public T popFromHead(){
if(head==null){
return null;
}
Node<T> cur=head;
if(head==tail){//如果链表中只有一个节点
head=null;
tail=null;
}else{
head=head.next;
cur.next=null;
head.last=null;
}
return cur.value;
}
//从尾部弹出节点
public T popFromBottom(){
if(head==null){
return null;
}
Node<T> cur=tail;
if(head==tail){//如果链表中只有一个节点
head=null;
tail=null;
}else{
tail=tail.last;
tail.next=null;
cur.last=null;
}
return cur.value;
}
}
(2)双向链表创建栈
public static class MyStack<T{
private DoubleEndsQueue<T> queue;
public MyStack(){
queue=new DoubleEndsQueue<T>();
}
//从头部插入从头部弹出，实现先进后出
//往栈中插入数据
public void push(T value){
queue.addFromHead(value);
}
//将数据弹出栈
public T pop(){
return queue.popFromHead();
}
//判断是否为空
public boolean isEmpty(){
return queue.isEmpty();
}
}
(3)双向链表创建队列
public static class MyQueue<T{
private DoubleEndsQueue<T> queue;
public MyStack(){
queue=new DoubleEndsQueue<T>();
}
//从头部插入从尾部弹出，实现先进先出
//往栈中插入数据
public void push(T value){
queue.addFromHead(value);
}
//将数据弹出栈
public T pop(){
return queue.popFromBottom();
}
//判断是否为空
public boolean isEmpty(){
return queue.isEmpty();
}
}
2.使用数组实现栈和队列
提示：只考虑固定大小数组
(1)数组实现队列：实现环形数组
public static class MyQueue{
private int[] arr;
private int pushi;//记录插入数据的位置
private int polli;//记录弹出数据的位置
private int size;//记录队列中的数据个数
private final int limit;//数组大小
//初始化数组
publish MyQueue(int limit){
arr=new int[limit];
pushi = 0;
polli=0;
size=0;
this.limit=limit;
}
//进队列
public void push(int value){
if(size==limit){
throw new RuntimeException("队列已满，不可再入队")
}
size++;
arr[pushi]=value;
pushi=nextIndex(pushi);
}
//出队列
public int pop(){
if(size==0){
throw new RuntimeException("栈为空");
}
size--;
int ans=arr[polli];
polli=nextIndex(polli);
return ans;
}
//判断是否为空
public boolean isEmpty(){
return size==0;
}
//如果现在的下标是i，返回下一个位置，
private int nextIndex(int i){
//判断i是否到了数组的最后一个位置，如果是，从0开始
return i<limit-1 ? i+1:0;
}
}
(2)数组实现栈
public static class MyStack{
private int[] arr;
private int size;//记录栈的数据大小
private final int limit;//数组大小
//初始化数组
publish MyQueue(int limit){
arr=new int[limit];
size=0;
this.limit=limit;
}
//进栈
public void push(int value){
if(size==limit){
throw new RuntimeException("队列已满，不可再入队")
}else{
size++;
arr[size]=value;
}
}
//出栈
public int pop(){
if(size==0){
throw new RuntimeException("栈为空");
}
size--;
int ans=arr[size];
return ans;
}
//判断是否为空
public boolean isEmpty(){
return size==0;
}
}
3.栈和队列的常见面试题
（1）实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能
1) pop、push、getMin操作的时间复杂度都是O(1)。
2）设计的栈类型可以使用现成的栈结构。实现思路：准备两个栈，一个栈为正常的数据栈Data，一个栈Min来存放最小值，每次插入一个新数据newNum，Data正常插入，插入Min中是每次要与栈顶比较大小
public static class MyStack2{
//创建两个栈
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack2(){
this.stackData=new Stack<Integer>();
this.stackMin=new Stack<Integer>();
}
public void push(int newNum){
//往stackMin中放数据时，需要将数据与Min栈顶的数据进行比较，
// 以确保Min插入的每一个数据都是最新的最小值
if(this.stackMin,isEnpty()){
this.stackMin.push(newNum);
}else if(newNum<this.getmin()){
this.stackMin.push(newNum);
}else{
int newMin =this.stackMin.peek();
this.stackMin.push(newMin);
}
this.stackData.push(newNum);
}
public int pop(){
if(this.stackData.isEmpty()){
throw new RuntimeException("栈为空");
}
this.stackMin.pop();
return this.stackData.pop();
}
public int getmin(){
if (this.stackMin.isEmpty()){
throw new RuntimeException("栈为空");
}
//返回栈栈顶数据
return this.stackMin.peek();
}
}
三、递归
判断递归的复杂度
Master公式
形如 T(N)= a * T(N/b)+O(N^d)(其中的a、b、d都是常数)的递归函数，可以直接通过Master公式来确定时间复杂度如果log(b,a)< d，复杂度为O(N^d)
如果log(b,a) > d,复杂度为O(N^log(b,a))
如果log(b,a) == d，复杂度为O(N^d * logN)
四、哈希表与有序表
1.哈希表（HashMap）
1)哈希表在使用层面上可以理解为一种集合结构
2)如果只有key，没有伴随数据value，可以使用HashSet结构
3)如果既有key，又有伴随数据value，可以使用HashMap结构
4)有无伴随数据，是HashMap和HashSet唯一的区别,实际结构是一回事
5)使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为o(1)，但是常数时间比较大
6)放入哈希表的东西，如果是基础类型，内部按值传递，内存占用是这个东西的大小
7)放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是8字节
2.有序表（TreeMap）
1)有序表在使用层面上可以理解为一种集合结构。
2)如果只有key，没有伴随数据value，可以使用set结构
3)如果既有key，又有伴随数据value，可以使用map结构
4)有无伴随数据是set与map的唯一区别，底层的实际结构是一回事。
5)有序表和哈希表的区别是，有序表把key按顺序组织起来，而哈希表完全不组织。
6)只要是有序表，他的常见操作的时间复杂度都是O(logN)