本文共 20269 字,大约阅读时间需要 67 分钟。
数据结构-线性表
- 数组ArrayList
- 链表LinkedList
- 栈Stack
- 队列Queue
- 哈希表(散列表)(单独摘出来)
- 树Tree
- 二叉树BinaryTree
- 二叉搜索树BinarySearchTree
- 平衡二叉树BalanceBinarySearchTree
- B树
- AVL树
- 红黑树
- 哈夫曼树
- Trie树
- 线性表是具有n个相同类型元素的有限序列(n>=0)
常见的线性表有:
- 数组ArrayList
- 链表LinkedList
- 栈Stack
- 队列Queue
- 哈希表(散列表)(单独摘出来)
一、 动态数组ArrayList
-
数组是一种顺序存储的线性表,所有元素的内存地址是连续的。
-
但在很多编程语言中,数组都有个致命的缺陷,无法动态修改容量
-
实际开发中,我们希望数组的容量是可以动态改变的。
1.动态数组接口设计
2.动态数组的设计
// 成员变量int size;int[] elements; // 常量private static final int DEFAULT_CAPATICY = 10;// 有参构造函数public ArrayList(int capaticy) { elements = new int[capaticy];}// 无参构造函数public ArrayList() { this(DEFAULT_CAPATICY);}
3.重要接口实现
3.1 添加元素-add(E element)
/** * 添加元素到最后面 * @param element */ public void add(int element) { add(size,element); }
3.2 打印数组
- 重写toString方法
- 在toString方法中将元素拼接成字符串
- 字符串拼接建议使用StringBuilder
/** * 重写toString方法 */ @Override public String toString() { // TODO Auto-generated method stub StringBuilder res = new StringBuilder(); res.append("size=").append(size).append(", ["); for(int i=0;i
3.3 删除元素-remove(int index)
/** * 删除index位置对应的元素 * @param index * @return */ public int remove(int index) { // 对index进行判断 rangeCheck(index); int oldElement = elements[index]; for(int i=index+1;i
3.4 添加元素-add(int index,int element)
/** * 往index位置添加元素 * @param index * @param element */ public void add(int index,int element) { // index判断可以往size位置添加 rangeForCheck(index); // 对其添加元素 for(int i=size;i>index;i--) { elements[i] = elements[i-1]; } elements[index] = element; size++; }
3.5 扩容
- 在add前进行检查当前数组的size与数组申请的大小比较
/** * 往index位置添加元素 * @param index * @param element */ public void add(int index,int element) { // index判断可以往size位置添加 rangeForCheck(index); // 对其进行判断是否需要扩容 checkForCapaticy(size+1); // 对其添加元素 for(int i=size;i>index;i--) { elements[i] = elements[i-1]; } elements[index] = element; size++; } /** * 检查容量并扩容 */ private void checkForCapaticy(int capaticy) { int oldCapaticy = elements.length; if(oldCapaticy >= capaticy) { return; } // 扩容 // 新容量为旧容量的1.5倍 int newCapaticy = oldCapaticy + oldCapaticy >> 1; int newElements[] = new int[newCapaticy]; for(int i=0;i
3.6 缩容
- 如果内存使用比较紧张,动态数组有比较多的剩余空间,可以考虑进行缩容操作
- 比如剩余空间占总容量的一半时,就进行缩容
- 注意:如果扩容倍数、缩容时机设计不得当,有可能会导致复杂度震荡。
3.7 泛型
- 使用泛型技术可以让动态数组更加通用,可以存放任何数据类型
package com.lcz.array;@SuppressWarnings("unchecked")public class ArrayList{ // 成员变量 int size; E[] elements; // 常量 private static final int DEFAULT_CAPATICY = 10; private static final int DEFAULT_NOT_FOUNT = -1; // 无参构造函数 public ArrayList() { this(DEFAULT_CAPATICY); } // 有参构造函数 public ArrayList(int capaticy) { capaticy = capaticy > DEFAULT_CAPATICY? capaticy:DEFAULT_CAPATICY; elements = (E[])new Object[capaticy]; } /** * 返回元素的数量 * @return */ public int size() { return size; } /** * 是否为空 * @return */ public boolean isEmpty() { return size==0; } /** * 是否包含某个元素 * @param element * @return */ public boolean contains(E element) { return indexOf(element) != DEFAULT_NOT_FOUNT; } /** * 添加元素到最后面 * @param element */ public void add(E element) { add(size,element); } private void outOfBounds(int index) { throw new IndexOutOfBoundsException("Index:" + index + ",Size:" + size); } private void rangeCheck(int index) { if(index<0 || index>=size) { outOfBounds(index); } } private void rangeForCheck(int index) { if(index<0 || index>size) { outOfBounds(index); } } /** * 返回index位置对应的元素 * @param index * @return */ public E get(int index) { // 对其进行index判断 rangeCheck(index); return elements[index]; } /** * 设置index位置的元素 * @param index * @param element * @return 原来的元素 */ public E set(int index,E element) { // 对其进行index判断 rangeCheck(index); E oldElement = elements[index]; elements[index] = element; return oldElement; } /** * 往index位置添加元素 * @param index * @param element */ public void add(int index,E element) { // index判断可以往size位置添加 rangeForCheck(index); // 对其进行判断是否需要扩容 checkForCapaticy(size+1); // 对其添加元素 for(int i=size;i>index;i--) { elements[i] = elements[i-1]; } elements[index] = element; size++; } /** * 检查容量并扩容 */ private void checkForCapaticy(int capaticy) { int oldCapaticy = elements.length; if(oldCapaticy >= capaticy) { return; } // 扩容 // 新容量为旧容量的1.5倍 int newCapaticy = oldCapaticy + oldCapaticy >> 1; E newElements[] = (E[])new Object[newCapaticy]; for(int i=0;i
3.8 对象数组
- 对象数组中存储的是对象的地址,而不是对象的值。
- 若对其改进,需对内存管理进行修改
3.9 null的处理
3.10 java.util.ArrayList
- JDK中内置了一个动态数组类:java.util.ArrayList
3.11 ArrayList是否能进一步优化?
对ArrayList添加一个first记录第一个位置的索引,这样不需要释放内存。(可参考后续的循环双端队列设计)
二、 链表LinkedList
1.单向链表
- 动态数组有明显的缺点-可能会造成内存空间的大量浪费
- 能否用到多少就申请多少内存?
- 链表就可以办到这一点
- 链表是一种链式存储的线性表,所有元素的内存地址不一定是连续的。
1.1 链表的设计
- 一个size,一个first指针
1.2 接口设计
- ArrayList和LinkedList方法作用相同,共同引申一个接口List
- 但ArrayList和LinkedList有几个方法实现相同,有几个方法实现不相同,这时候添加一个abstract类
- 最后arraylist和linkedlist继承抽象类
1.3 重要接口实现
1.3.1 清空元素-clear()
@Overridepublic void clear() { // TODO Auto-generated method stub size = 0; first = null;}
1.3.2 添加元素-add(int index,E element)
- node方法用于获取index位置的节点
/** * node方法用于获取index位置的结点 * @param index * @return */ private Nodenode(int index){ rangeCheck(index); Node node = first; for(int i=0;i
- 添加元素 注意index 0 的位置
@Override public void add(int index, E element) { rangeForAddCheck(index); // TODO Auto-generated method stub if(index == 0) { first = new Node(element,first); }else { Nodepre = node(index-1); pre.next = new Node(element,pre.next); } size ++; }
1.3.3 删除元素-remove(int index)
@Override public E remove(int index) { // TODO Auto-generated method stub rangeCheck(index); Noderes = first; if(index == 0 ) { res = first; first = first.next; }else { Node pre = node(index-1); res = pre.next; pre.next = pre.next.next; } size--; return res.element; }
1.3.4 indexOf & toString方法
@Override public int indexOf(E element) { // TODO Auto-generated method stub if(element==null) { Nodenode = first; for(int i=0;i node = first; for(int i=0;i node(int index){ rangeCheck(index);
2.双向链表
- 之前所学的链表,也被称为单向链表
- 使用双向链表可以提升链表的综合性能
2.1 双向链表的设计
- 当双向链表只有一个元素时
2.2.重要接口的设计
2.2.1 获取index对应位置的节点
** * 获取index位置对应的节点对象 * @param index * @return */private Nodenode(int index) { rangeCheck(index); if (index < (size >> 1)) { Node node = first; for (int i = 0; i < index; i++) { node = node.next; } return node; } else { Node node = last; for (int i = size - 1; i > index; i--) { node = node.prev; } return node; }}
2.2.2 添加元素-add(int index,E element)
- 添加考虑几种情况
- 尾部插入和空加入
- 正常加入
- 头部加入
@Override public void add(int index, E element) { rangeCheckForAdd(index); // size == 0 // index == 0 if (index == size) { // 往最后面添加元素 NodeoldLast = last; last = new Node<>(oldLast, element, null); if (oldLast == null) { // 这是链表添加的第一个元素 first = last; } else { oldLast.next = last; } } else { Node next = node(index); Node prev = next.prev; Node node = new Node<>(prev, element, next); next.prev = node; if (prev == null) { // index == 0 first = node; } else { prev.next = node; } } size++; }
2.2.3 删除元素-remove(int index,E element)
- 添加考虑几种情况
- prev为空
- next为空
@Override public E remove(int index) { rangeCheck(index); Nodenode = node(index); Node prev = node.prev; Node next = node.next; if (prev == null) { // index == 0 first = next; } else { prev.next = next; } if (next == null) { // index == size - 1 last = prev; } else { next.prev = prev; } size--; return node.element; }
2.2.4 双向链表 vs 动态数组
-
动态数组:开辟、销毁内存空间的次数相对较少,但可能造成内存空间的浪费
-
双向链表:开辟、销毁内存空间的次数相比较多,但不会造成内存空间的浪费
-
如果频繁在尾部进行添加、删除操作,动态数组、双向链表均可选择
-
如果频繁在头部进行添加、删除操作,建议选择使用双向链表
-
如果有频繁的在任意位置添加、删除操作,建议选择使用双向链表
-
如果有频繁的查询操作,建议选择使用动态数组
-
如果有了双向链表,单向链表是否就没有任何用处了?
- 并非如此,在哈希表的设计中就用到了单链表
- hashmap使用的是单链表;而在linkedhashmap中使用的双链表
3.单向循环链表
3.1 单向循环链表的设计
单向循环链表-只有1个节点
3.2 重要接口设计
3.2.1 单向循环链表-add(int index, E element)
@Override public void add(int index, E element) { rangeCheckForAdd(index); if (index == 0) { NodenewFirst = new Node<>(element, first); // 拿到最后一个节点 Node last = (size == 0) ? newFirst : node(size - 1); last.next = newFirst; first = newFirst; } else { Node prev = node(index - 1); prev.next = new Node<>(element, prev.next); } size++; }
3.2.2 单向循环链表-remove(int index)
@Overridepublic E remove(int index) { rangeCheck(index); Nodenode = first; if (index == 0) { if (size == 1) { first = null; } else { Node last = node(size - 1); first = first.next; last.next = first; } } else { Node prev = node(index - 1); node = prev.next; prev.next = node.next; } size--; return node.element;}
单向循环链表,主要考虑头结点位置的插入和删除,插入的时候头结点是否有节点
4.双向循环链表
4.1 双向循环链表的设计
双向循环链表-只有一个节点
4.2 重要接口设计
4.2.1 双向循环链表-add(int index,E element)
@Overridepublic void add(int index, E element) { rangeCheckForAdd(index); // size == 0 // index == 0 if (index == size) { // 往最后面添加元素 NodeoldLast = last; last = new Node<>(oldLast, element, first); if (oldLast == null) { // 这是链表添加的第一个元素 first = last; first.next = first; first.prev = first; } else { oldLast.next = last; first.prev = last; } } else { Node next = node(index); Node prev = next.prev; Node node = new Node<>(prev, element, next); next.prev = node; prev.next = node; if (next == first) { // index == 0 first = node; } } size++;}
4.2.2 双向循环链表-remove(int index)
@Overridepublic E remove(int index) { rangeCheck(index); return remove(node(index));}private E remove(Nodenode) { if (size == 1) { first = null; last = null; } else { Node prev = node.prev; Node next = node.next; prev.next = next; next.prev = prev; if (node == first) { // index == 0 first = next; } if (node == last) { // index == size - 1 last = prev; } } size--; return node.element;}
4.3 约瑟夫环的问题
在单向循环链表中增设一个成员变量,三个成员方法来解决
- current:用于指向某个节点
- void reset(): 让current指向头结点first
- E next(): 让current往后走一步,也就是current = current.next
- E remove():删除current指向的节点,删除成功后让current指向下一个节点
public void reset() { current = first;}public E next() { if (current == null) return null; current = current.next; return current.element;}public E remove() { if (current == null) return null; Nodenext = current.next; E element = remove(current); if (size == 0) { current = null; } else { current = next; } return element;}
三、栈(Stack)
- 栈是一种特殊的线性表,只能在一端进行操作
- 往栈中添加元素的操作,一般叫做push,入栈
- 从栈中移除元素的操作,一般叫做pop,出栈
- 后进先出的原则
1.栈的接口设计
- int size(); // 元素的数量
- boolean isEmpty(); // 是否为空
- void push(E element); // 入栈
- E pop(); //出栈
- E peek(); //获取栈顶元素
- void clear(); //清空
栈的实现本次基本之前的动态数组、链表。不采取继承的方式,而是基于成员变量的方法。
package com.mj;import com.mj.list.ArrayList;import com.mj.list.List;public class Stack{ private List list = new ArrayList<>(); public void clear() { list.clear(); } public int size() { return list.size(); } public boolean isEmpty() { return list.isEmpty(); } public void push(E element) { list.add(element); } public E pop() { return list.remove(list.size() - 1); } public E top() { return list.get(list.size() - 1); }}
2.java.util.Stack
java中的实现是通过继承Vector来实现的。
3.栈的应用
- 实现方式:通过两个栈来实现,一个栈来存取,另外一个栈存取前面一个栈出栈的
4.栈的练习题
1.有效括号
解题思路:
1.遇见左括号,将左字符入栈
2.遇见右括号
- 如果栈是空的,说明括号无效
- 如果栈不为空,将栈顶字符出栈,与右字符匹配
- 如果匹配不成功,则括号无效
- 如果左右字符匹配,继续扫描下一个字符
3.所有字符扫描完毕后
栈为空,说明括号无效
栈不为空,说明括号无效
class Solution { public boolean isValid(String s) { HashMaphashMap = new HashMap<>(); hashMap.put('(',')'); hashMap.put('{','}'); hashMap.put('[',']'); Stack stack = new Stack<>(); for(int i=0;i
四、 队列(Queue)
队列是一种特殊的线性表,只能在头尾两端进行操作。
- 队尾(rear):只能从队尾添加元素,一般叫做enQueue,入队
- 对头(front):只能从对头移除元素,一般叫做deQueue,出队
- 先进先出的原则,First In First Out,FIFO
1.队列
1.1 队列的端口设计
- int size(): // 元素的数量
- boolean isEmpty(); //是否为空
- void clear(); //清空
- void enQueue(E element); // 入队
- E deQueue(); //出队
- E front(); //获取队列的头元素
队列本次实现使用双向链表来实现,因为队列主要是往头尾操作元素。
1.2 队列的接口实现
public class Deque{ private List list = new LinkedList (); /** * 返回队列的长度 * @return */ public int size() { return list.size(); } /** * 返回队列是否为空的判断 * @return */ public boolean isEmpty() { return list.isEmpty(); } /** * 清空队列中的元素 */ public void clear() { list.clear(); } /** *入队操作 * @param element */ public void enQueue(E element) { list.add(element); } /** * 出队操作 * @return */ public E deQueue() { E element = list.remove(0); return element; } /** * 获取队列的头元素 * @return */ public E front() { E element = list.get(0); return element; }}
1.3 队列的练习-用栈实现队列
解题思路:
- 准备两个栈:inStack, outStack
- 入队时,push到inStack中
- 出队时,
- 如果outStack为空,将inStack所有元素逐一弹出,push到outStack,outStack弹出栈顶元素
- 如果outStack不为空,outStack弹出栈顶元素
class MyQueue { /** Initialize your data structure here. */ Stackstack_first = null; Stack stack_second = null; /** * 初始化队列 */ public MyQueue() { stack_first = new Stack (); stack_second = new Stack (); } /** * 将元素x推到队列的末尾 */ /** Push element x to the back of queue. */ public void push(int x) { // 直接入栈1 stack_first.push(x); } /** * 从队列的开头移除并返回元素 */ /** Removes the element from in front of queue and returns that element. */ public int pop() { // 判断栈2 if(stack_second.isEmpty()) { // 栈2为空的话 // 先将栈1都弹出来 while(!stack_first.isEmpty()) { stack_second.push(stack_first.pop()); } return stack_second.pop(); }else { // 栈2不为空的话 return stack_second.pop(); } } /** * 返回队列开头的元素 */ /** Get the front element. */ public int peek() { if(stack_second.isEmpty()) { while(!stack_first.isEmpty()) { stack_second.push(stack_first.pop()); } return stack_second.peek(); }else { return stack_second.peek(); } } /** * 判断队列是否为空 */ /** Returns whether the queue is empty. */ public boolean empty() { return stack_first.isEmpty()&&stack_second.isEmpty(); }}
1.4 java.util.Queue的实现
- 入队操作:offer
- 出队操作:poll
- 获取对头:peek
2. 双端队列(Deque)
双端队列是能在头尾两端添加、删除的队列。
2.1 双端队列重要接口设计
- int size(); //元素的数量
- boolean isEmpty(); //是否为空
- void clear(); //清空
- void enQueueRear(E element); //从队尾入队
- E deQueueFront(); //从队头出队
- void enQueueFront(); //从队头入队
- E deQueueRear(); //从队尾出队
- E front(); //获取队列的头元素
- E rear(); //获取队列的尾元素
2.2 双端队列重要接口实现
public class Deque{ private List list = new LinkedList (); /** * 获取队列的数量 * @return */ public int size() { return list.size(); } /** * 判断队列是否为空 * @return */ public boolean isEmpty() { return list.isEmpty(); } /** * 清空队列 */ public void clear() { list.clear(); } /** * 从队尾入队 * @param element */ public void enQueueRear(E element) { list.add(element); } /** * 从队头入队 * @param element */ public void enQueueFront(E element) { list.add(0,element); } /** * 从队头出队 */ public E deQueueFront() { return list.remove(0); } /** * 从队尾出队 */ public E deQueueRear() { return list.remove(list.size()-1); } /** * 获取队列的头元素 * @return */ public E front() { return list.get(0); } /** * 获取队列的尾元素 * @return */ public E rear() { return list.get(list.size()-1); }}
3. 循环队列(Circle Queue)
队列底层也可以使用动态数组实现,并且各项接口也可以优化到O(1)的时间复杂度。
这个用数组实现并且优化之后的队列也叫作:循环队列。
3.1 循环队列的端口设计
- int size(); //获取队列的大小
- boolean isEmpty(); //判断队列是否为空
- void clear(); //清空队列
- void enQueue(); //入队
- E deQuque(); //出队
- E front(); //队头元素
3.2 循环队列的接口实现
public class CircleQueue{ int size; int front; E elements[]; private static final int DEFAULT_CAPATICY = 10; /** * 构造函数 */ public CircleQueue() { elements = (E[])new Object[DEFAULT_CAPATICY]; } /** * 获取循环队列的大小 * @return */ public int size() { return size; } /** * 判断队列是否为空 * @return */ public boolean isEmpty() { return size==0; } /** * 清空队列 */ public void clear() { for(int i=0;i =capaticy) return; int newCapaticy = oldCapaticy + oldCapaticy >> 1; E[] newElements = (E[])new Object[newCapaticy]; for(int i=0;i
4. 循环双端队列
- 循环双端队列:可以进行两端添加、删除操作的循环队列。
4.1 循环双端队列的端口设计
- int size(); //获取队列的大小
- boolean isEmpty(); //判断队列是否为空
- void clear(); //清空队列
- void enQueueRear(); //从队尾入队
- void enQueueFront(); //队头入队
- E deQuqueFront(); /从队头/出队
- E deQuqueRear(); //从队尾出队
- E front(); //队头元素
- E rear(); //队尾元素
4.2 循环双端队列的端口实现
public class CircleDeque{ int size; int front; E elements[]; private static final int DEFAULT_CAPATICY = 10; /** * 构造函数 */ public CircleDeque() { elements = (E[])new Object[DEFAULT_CAPATICY]; } /** * 获取循环队列的大小 * @return */ public int size() { return size; } /** * 判断队列是否为空 * @return */ public boolean isEmpty() { return size==0; } /** * 清空队列 */ public void clear() { for(int i=0;i =capaticy) return; int newCapaticy = oldCapaticy + oldCapaticy >> 1; E[] newElements = (E[])new Object[newCapaticy]; for(int i=0;i
5. 队列的应用-用队列实现栈
实现思路:
- 准备两个队列用于实现栈 一个queue_in 一个queue_out
- 入栈的话 queue_in接收元素 并将queue_out中的元素全部排出并接收 之后queue_in 和queue_out互换
- 出栈的话 queue_out出队列即可
class MyStack { Queuequeue_in; Queue queue_out; /** Initialize your data structure here. */ public MyStack() { queue_in = new LinkedList<>(); queue_out = new LinkedList<>(); } /** Push element x onto stack. */ public void push(int x) { queue_in.offer(x); while(!queue_out.isEmpty()){ queue_in.offer(queue_out.poll()); } Queue temp_queue = queue_in; queue_in = queue_out; queue_out = temp_queue; } /** Removes the element on top of the stack and returns that element. */ public int pop() { return queue_out.poll(); } /** Get the top element. */ public int top() { return queue_out.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue_out.isEmpty(); }}
ength;
} return index%elements.length; }/** * 容量扩充 */private void ensureCapaticy(int capaticy) { int oldCapaticy = elements.length; if(oldCapaticy>=capaticy) return; int newCapaticy = oldCapaticy + oldCapaticy >> 1; E[] newElements = (E[])new Object[newCapaticy]; for(int i=0;i
}
## 5. 队列的应用-用队列实现栈> 实现思路:>> - 准备两个队列用于实现栈 一个queue_in 一个queue_out> - 入栈的话 queue_in接收元素 并将queue_out中的元素全部排出并接收 之后queue_in 和queue_out互换> - 出栈的话 queue_out出队列即可```javaclass MyStack { Queuequeue_in; Queue queue_out; /** Initialize your data structure here. */ public MyStack() { queue_in = new LinkedList<>(); queue_out = new LinkedList<>(); } /** Push element x onto stack. */ public void push(int x) { queue_in.offer(x); while(!queue_out.isEmpty()){ queue_in.offer(queue_out.poll()); } Queue temp_queue = queue_in; queue_in = queue_out; queue_out = temp_queue; } /** Removes the element on top of the stack and returns that element. */ public int pop() { return queue_out.poll(); } /** Get the top element. */ public int top() { return queue_out.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue_out.isEmpty(); }}
转载地址:https://codingchaozhang.blog.csdn.net/article/details/109616521 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!