数据结构基础
1.数组
（1）数组基础：把数据码成一排进行存放
- 优点：快速查询
-
（2）二次封装数组（添加与删除元素 / 动态数组 ）
（3）动态数组建立
```java // 通过静态数组来实现一个动态数组 // 建立一个动态数组，需要首先有一个静态数组，还有一个默认属性size public class Array
{ private E[] data; private int size; // 默认数组大小为15 public Array(){
this(15);
}
// 用户自己定义数组容量 public Array(int capacity){
data = (E[]) new Object[capacity];size = 0;
}
// 获取元素存入的元素个数 size public int getSize(){
return size;
}
// capacity 表示可容纳的元素个数 public int getCapacity(){
return data.length;
}
// 判断数组是否为空 public boolean isEmpty(){
return size == 0;
} // 对数组大小进行改变 public E[] resize(int capacity){
E[] temp = (E[]) new Object[capacity];for(int i = 0; i < size; i++){temp[i] = data[i];}data = temp;return data;
}
// 在 index 位置添加元素 public void add(int index, E e){
if(index > data.length - 1 || index < 0){throw new IllegalArgumentException("put of index");}if(size == data.length){resize(2*data.length);}for(int i = size - 1; i >= index; i++){data[i+1] = data[i];}data[index] = e;size++;
}
// 在头部添加元素 public void addFirst(E e){
add(0,e);
}
// 在尾部添加元素 public void addLast(E e){
add(size,e);
}
// 删除 index 处元素, 并返回删除的元素 public E remove(int index){
if(index < 0 || index > data.length - 1){throw new IllegalArgumentException("put of index");}E res = data[index];for(int i = index; i < size - 1 ; i++){data[i] = data[i+1];}size--;if( size == data.length / 4 && data.length / 2 != 0 ){resize(data.length / 2);}return res;
}
// 删除头部元素 public void removeFirst(){
remove(0);
}
// 删除尾部元素 public void removeLast(){
reomve(size - 1);
}
/*** 实现 findAll 和 removeAllElement 方法*/// finaAll 找到某一元素在数组中的所有索引public int[] findAll(E e){int[] target = new int[size];int j = 0;for(int i = 0; i < size; i++){if(data[i].equals(e)){target[j] = i;j++;}}return Arrays.copyOfRange(target,0,j);}public E removeAllElement(E e){int[] target = findAll(e);for(int index :target){remove(index);}return e;}@Overridepublic String toString() {StringBuilder res = new StringBuilder();for(int i = 0; i <size; i++){res.append(data[i] + " ");}return res.toString();}
}
<a name="97bcd0d4"></a>
#### 数组的时间复杂度分析：
- 添加操作：
- addLast ( e ) : O(1)
- addFirst ( e ) : O ( n )
- add ( index , e ): O( n / 2 )
- 删除操作：时间复杂度为 O（n）
- removeLast（e） O(1)
- removeFirst（e） O(n)
- remove（index , e） O(n/2) = O(n)
- 修改： set(index , e) O(1)
- 查询：
- get ( index ) O (1)
- contains( e ) O (n)
- find( e ) O (n)
- 动态修改数组大小 ：resize( ) => O(1)
- 每次进行 addLast() 操作， 假设 Capacity 为 8, 则九次操作add + 8次元素转移操作，才触发一次resize() 操作 。
- 进行 2n+1次基本操作，才产生一次resize()，即触发一次resize() 相当于进行两次基本操作，这样来看 addLast ( ) 的时间复杂度为 O(1)
<a name="fe9f351b"></a>
#### 复杂度震荡
思考 addLast( ) 与 removeLast( ) 情况<br /><br />假如一旦超过，或者 size == capacity / 2; 当频繁进行addLast() 与 removeLast() 时，两次基本操作，就产生两次resize() 操作， 而resize（） 操作 为 O（n）, 则二者的时间复杂度为 O(n) 级别。算法退化
<a name="J5YO4"></a>
## 2.链表：
- **最简单的动态数据结构**
- **可以更深入的了解指针**
- **更深入了解递归**
<a name="QBDQr"></a>
### 一、节点(node)
class Nod E e; Node next; }
数据存储在Node中
- 优点：不需要考虑固定容量的问题
- 缺点：不能直接访问index 处的元素
对于数组：由于是在内存中连续分配空间，因此可以直接获取元素，复杂度为O(1)
<a name="vxgkW"></a>
### 二、链表的实现
```java
// 实现链表 使用虚拟头节点
public class LinkedList<E>{
private class Node{
private E e;
private Node next;
public Node(){
this(null,null);
}
public Node(E value){
this(value,null);
}
public Node(E value, Node next){
this.e = value;
this.next = next;
}
}
private Node dummyHead;
private size;
public LinkedList(){
dummyHead = null;
size = 0;
}
// 获取 index 处元素
public E getIndex(int index){
if(index < 0 || index > size){
throw new IllegalArgumentException("add failed");
}
Node prev = dummyHead;
for(int i = 0 ; i < index; i++){
prev = prev.next;
}
Node res = prev.next;
return res.e;
}
// 在 index 处添加元素
public void add(int index, E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("add failed");
}
Node prev = dummyHead;
for(int i = 0; i < index; i++){
prev = prev.next; // 获取 index - 1 处的Node
}
E res = new Node(e, prev.next);
prev.next = res;
size++;
}
// 在头部添加元素
public void addFirst(E e){
add(0,e);
}
// 在尾部田添加元素
public void addLast(E e){
add(size,e);
}
// 删除 index 处元素
public E remove(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("add failed");
}
Node prev = dummyHead;
for(int i = 0 ; i < index; i++){
prev = prev.next; // 获取index - 1 的 Node
}
E res = prev.next // 获取 index 处的 Node
prev.next = res.next // 把index - 1 的 next 替换为 index.next
res.next = null;
size--;
return res.e;
}
// 删除尾部元素
public E removeLast(){
return remove(size - 1);
}
// 删除头部元素
public E removeFirst(){
return remove(0);
}
}
// 不使用虚拟头节点
public class LinkedList<E>{
private class Node{
public E e;
public Node next;
public Node(){
this(null,null);
}
public Node(E value){
this(value,null);
}
public Node(E value, Node next){
this.e = value;
this.next = next;
}
}
private int size;
private Node head;
public LinkedList(){
size = 0;
head = null;
}
// 添加元素
public void addIndex(int index, E e){
if(index < 0 || index >= size){
throw new IllegalArgumentException("add failed");
}
if(size == 0){
head = new Node(e);
}else{
E prev = head;
for(int i = 0 ; i < index - 1; i++){
prev = prev.next; // 获取 index - 1 处的 Node
}
// 刚结束循环的 Node 为 index - 1 的 Node
Node newNode = new Node(e, prev.next); // newNode 的 next 为 index 处的 Node
prev.next = newNode;
}
size++;
}
// 删除元素
public E removeIndex(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("add failed");
}
E prev = head;
for(int i = 0; i < index - 1; i++){
prev = prev.next; // 获取到的 Node 为 index - 1 处元素
}
E res = prev.next // 获取index 处 Node
prev.next = res.next; // 将 Index - 1 的 Node 替换为 index 的 Node
size--;
return res;
}
}
三、使用链表实现队列
// 实现队列 先入先出
// 队列的操作
//void enqueue(E) O(1) 从尾部添加元素 addLast（）
//E dequeue() O(n) 从队首删除元素 removeFirst()
//E front() O(1)
//int getSize() O(1)
//boolean isEmpty() O(1)
public class Queue<E>{
private LinkedList<E> data;
public Queue(){
data = new LinkedList<>();
size = 0;
}
// 入队
public void enqueue(E e){
data.addLast(e);
}
// 出队
public E dequeue(){
return data.removeFirst();
}
// 获取队顶元素
public E front(){
return data.getIndex(0);
}
}
public class LinkedList<E> implements Queue<E>{
//注意存在头指针和尾指针
private class Node{
public E e;
public Node next;
public Node(){
this(null,null);
}
public Node(E value){
this(value,null);
}
public Node(E value, Node next){
this.e = value;
this.next = next;
}
}
private Node head, tail;
private int size;
public LinkedList(){
size = 0;
head = 0;
tail = 0;
}
// 从尾部添加元素
public void enqueue(E e){
if(tail = null){
tail = new Node(e);
head = tail;
} else {
tail.next = new Node(e);
tail = tail.next;
}
size++;
}
// 从头部删除元素, 消除元素与链表的关系
public E dequeue(){
if(size == 0){
throw new IllegalArgumentException("remove failed");
}
Node res = head;
head = head.next;
res.next = null;
size--;
return res;
}
}
四、链表与递归：
递归就是把问题转化为复杂度更小的问题 / 求解最基本
- leetcode 问题
https://leetcode-cn.com/problems/remove-linked-list-elements/
// 使用递归
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return head;
}
head.next = removeElements(head.next, val);
if(head.val == val){
return head.next;
}else{
return head;
}
}
}
有序与无序集合
- 有序集合的元素具有顺序性（基于搜索树实现）
- 无序集合的元素没有顺序性 (基于哈希表实现)
-
3.Set and Map （集合与映射）
// 都可以使用链表和树实现，只要设置 Node 中增加key, Value 即可
Set：不允许出现重复元素
set实际上是一个接口， 实现了 Collection
主要有以下几个方法：
// 获取元素个数
int size()
// 查看 Set 是否为空
boolean isEmpty()
// 查看 Set 是否包含元素
boolean contains(Object o)
// 添加元素
boolean add(E e)
// 删除元素
boolean remove(Object o)
HashSet实现：
public class HashSet
Set<Integer> set = new HashSet<>();// 创建Set，为 AbstractSet<E> 的子类
private transient HashMap<E,Object> map; // 底层由HashMap实现
Map(键值对)：
Map实际上也是接口：
Map<K,V>;
// 主要的方法
int size()
boolean isEmpty();
boolean containsValue(Object value);
boolean containsKey(Object key);
V get(Object key);
V put(K key, V value);
V remove(Object key);
// 替换元素
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
若有收获，就点个赞吧
0 人点赞
