1.数组
1.1数组的特点
在Java中，数组是用来存放同一种数据类型的集合，并且只能存放同一种数据类型。
//只声明了类型和长度 数据类型[] 数组名称 = new 数据类型[数组长度]; //声明了类型，初始化赋值，大小由元素个数决定 数据类型[] 数组名称 = {数组元素1，数组元素2，......}
例如：整型数组
例如：对象数组
- 物理结构特点：
- 申请内存：一次申请一大段连续的空间，一旦申请到了，内存就固定了。
- 不能动态扩展(初始化给大了，浪费；给小了，不够用)，插入快，删除和查找慢。
- 存储特点：所有数据存储在这个连续的空间中，数组中的每一个元素都是一个具体的数据（或对象），所有数据都紧密排布，不能有间隔。
- 如下图：
1.2自定义数组
class Array { private Object[] elementData; private int size; public Array(int capacity){ elementData = new Object[capacity]; } /** * 添加元素 * @param value */ public void add(Object value){ if(size >= elementData.length){ throw new RuntimeException("数组已满，不可添加"); } elementData[size] = value; size++; } /** * 查询元素value在数组中的索引位置 * @param value * @return */ public int find(Object value){ for (int i = 0; i < size; i++) { if(elementData[i].equals(value)){ return i; } } return -1; } /** * 从当前数组中移除首次出现的value元素 * @param value * @return */ public boolean delete(Object value){ int index = find(value); if(index == -1){ return false; } for(int i = index;i < size - 1;i++){ elementData[i] = elementData[i + 1]; } elementData[size - 1] = null; size--; return true; } /** * 将数组中首次出现的oldValue替换为newValue * @param oldValue * @param newValue * @return */ public boolean update(Object oldValue,Object newValue){ int index = find(oldValue); if(index == -1){ return false; } elementData[index] = newValue; return true; } /** * 遍历数组中所有数据 */ public void print(){ System.out.print("{"); for (int i = 0; i < size; i++) { if(i == size - 1){ System.out.println(elementData[i] + "}"); break; } System.out.print(elementData[i] + ","); } } } //测试类 public class ArrayTest { public static void main(String[] args) { Array arr = new Array(10); arr.add(123); arr.add("AA"); arr.add(345); arr.add(345); arr.add("BB"); arr.delete(345); arr.update(345,444); arr.print(); } }
2.链表
2.1链表的特点
- 逻辑结构：线性结构
- 物理结构：不要求连续的存储空间
- 存储特点：链表由一系列结点node（链表中每一个元素称为结点）组成，结点可以在代码执行过程中动态创建。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
- 常见的链表结构有如下的形式：
2.2自定义链表
2.2.1自定义单向链表
/* 单链表中的节点。 节点是单向链表中基本的单元。 每一个节点Node都有两个属性： 一个属性：是存储的数据。 另一个属性：是下一个节点的内存地址。 */ public class Node { // 存储的数据 Object data; // 下一个节点的内存地址 Node next; public Node(){ } public Node(Object data, Node next){ this.data = data; this.next = next; } }
/* 链表类(单向链表) */ public class Link<E> { // 头节点 Node header; private int size = 0; public int size(){ return size; } // 向链表中添加元素的方法（向末尾添加） public void add(E data){ //public void add(Object data){ // 创建一个新的节点对象 // 让之前单链表的末尾节点next指向新节点对象。 // 有可能这个元素是第一个，也可能是第二个，也可能是第三个。 if(header == null){ // 说明还没有节点。 // new一个新的节点对象，作为头节点对象。 // 这个时候的头节点既是一个头节点，又是一个末尾节点。 header = new Node(data, null); }else { // 说明头不是空！ // 头节点已经存在了！ // 找出当前末尾节点，让当前末尾节点的next是新节点。 Node currentLastNode = findLast(header); currentLastNode.next = new Node(data, null); } size++; } /** * 专门查找末尾节点的方法。 */ private Node findLast(Node node) { if(node.next == null) { // 如果一个节点的next是null // 说明这个节点就是末尾节点。 return node; } // 程序能够到这里说明：node不是末尾节点。 return findLast(node.next); // 递归算法！ } /*// 删除链表中某个数据的方法 public void remove(Object obj){ //略 } // 修改链表中某个数据的方法 public void modify(Object newObj){ //略 } // 查找链表中某个元素的方法。 public int find(Object obj){ //略 }*/ }
2.2.2自定义双向链表
/* 双向链表中的节点。 */ public class Node<E> { Node prev; E data; Node next; Node(Node prev, E data, Node next) { this.prev = prev; this.data = data; this.next = next; } }
public class MyLinkedList<E> implements Iterable<E>{ private Node first; //链表的首元素 private Node last; //链表的尾元素 private int total; public void add(E e){ Node newNode = new Node(last, e, null); if(first == null){ first = newNode; }else{ last.next = newNode; } last = newNode; total++; } public int size(){ return total; } public void delete(Object obj){ Node find = findNode(obj); if(find != null){ if(find.prev != null){ find.prev.next = find.next; }else{ first = find.next; } if(find.next != null){ find.next.prev = find.prev; }else{ last = find.prev; } find.prev = null; find.next = null; find.data = null; total--; } } private Node findNode(Object obj){ Node node = first; Node find = null; if(obj == null){ while(node != null){ if(node.data == null){ find = node; break; } node = node.next; } }else{ while(node != null){ if(obj.equals(node.data)){ find = node; break; } node = node.next; } } return find; } public boolean contains(Object obj){ return findNode(obj) != null; } public void update(E old, E value){ Node find = findNode(old); if(find != null){ find.data = value; } } @Override public Iterator<E> iterator() { return new Itr(); } private class Itr implements Iterator<E>{ private Node<E> node = first; @Override public boolean hasNext() { return node!=null; } @Override public E next() { E value = node.data; node = node.next; return value; } } }
自定义双链表测试：
public class MyLinkedListTest { public static void main(String[] args) { MyLinkedList<String> my = new MyLinkedList<>(); my.add("hello"); my.add("world"); my.add(null); my.add(null); my.add("java"); my.add("java"); my.add("xiaoyang"); System.out.println("一共有：" + my.size()); System.out.println("所有元素："); for (String s : my) { System.out.println(s); } System.out.println("-------------------------------------"); System.out.println("查找java,null,haha的结果："); System.out.println(my.contains("java")); System.out.println(my.contains(null)); System.out.println(my.contains("haha")); System.out.println("-------------------------------------"); System.out.println("替换java,null后："); my.update("java","JAVA"); my.update(null,"songhk"); System.out.println("所有元素："); for (String s : my) { System.out.println(s); } System.out.println("-------------------------------------"); System.out.println("删除hello，JAVA,null，xiaoyang后："); my.delete("hello"); my.delete("JAVA"); my.delete(null); my.delete("xiaoyang"); System.out.println("所有元素："); for (String s : my) { System.out.println(s); } } }
3.栈
3.1栈的特点
- 栈（Stack）又称为堆栈或堆叠，是限制仅在表的一端进行插入和删除运算的线性表。
- 栈按照先进后出(
FILO,first in last out)的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶。每次删除（退栈）的总是删除当前栈中最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。 - 核心类库中的栈结构有
Stack和LinkedList。
Stack就是顺序栈，它是Vector的子类。LinkedList是链式栈。
- 体现栈结构的操作方法：
peek()方法：查看栈顶元素，不弹出pop()方法：弹出栈push(E e)方法：压入栈
- 时间复杂度:
- 索引: O(n)
- 搜索: O(n)
- 插入: O(1)
- 移除: O(1)
- 如图所示：
3.2 Stack使用举例
public class TestStack { /* * 测试Stack * */ @Test public void test1(){ Stack<Integer> list = new Stack<>(); list.push(1); list.push(2); list.push(3); System.out.println("list = " + list); System.out.println("list.peek()=" + list.peek()); System.out.println("list.peek()=" + list.peek()); System.out.println("list.peek()=" + list.peek()); /* System.out.println("list.pop() =" + list.pop()); System.out.println("list.pop() =" + list.pop()); System.out.println("list.pop() =" + list.pop()); System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException */ while(!list.empty()){ System.out.println("list.pop() =" + list.pop()); } } /* * 测试LinkedList * */ @Test public void test2(){ LinkedList<Integer> list = new LinkedList<>(); list.push(1); list.push(2); list.push(3); System.out.println("list = " + list); System.out.println("list.peek()=" + list.peek()); System.out.println("list.peek()=" + list.peek()); System.out.println("list.peek()=" + list.peek()); /* System.out.println("list.pop() =" + list.pop()); System.out.println("list.pop() =" + list.pop()); System.out.println("list.pop() =" + list.pop()); System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException */ while(!list.isEmpty()){ System.out.println("list.pop() =" + list.pop()); } } }
3.3 自定义栈
public class MyStack { // 向栈当中存储元素，我们这里使用一维数组模拟。存到栈中，就表示存储到数组中。 // 为什么选择Object类型数组？因为这个栈可以存储java中的任何引用类型的数据 private Object[] elements; // 栈帧，永远指向栈顶部元素 // 那么这个默认初始值应该是多少。注意：最初的栈是空的，一个元素都没有。 //private int index = 0; // 如果index采用0，表示栈帧指向了顶部元素的上方。 //private int index = -1; // 如果index采用-1，表示栈帧指向了顶部元素。 private int index; /** * 无参数构造方法。默认初始化栈容量10. */ public MyStack() { // 一维数组动态初始化 // 默认初始化容量是10. this.elements = new Object[10]; // 给index初始化 this.index = -1; } /** * 压栈的方法 * @param obj 被压入的元素 */ public void push(Object obj) throws Exception { if(index >= elements.length - 1){ //方式1： //System.out.println("压栈失败，栈已满！"); //return; //方式2： throw new Exception("压栈失败，栈已满！"); } // 程序能够走到这里，说明栈没满 // 向栈中加1个元素，栈帧向上移动一个位置。 index++; elements[index] = obj; System.out.println("压栈" + obj + "元素成功，栈帧指向" + index); } /** * 弹栈的方法，从数组中往外取元素。每取出一个元素，栈帧向下移动一位。 * @return */ public Object pop() throws Exception { if (index < 0) { //方式1： //System.out.println("弹栈失败，栈已空！"); //return; //方式2： throw new Exception("弹栈失败，栈已空！"); } // 程序能够执行到此处说明栈没有空。 Object obj = elements[index]; System.out.print("弹栈" + obj + "元素成功，"); elements[index] = null; // 栈帧向下移动一位。 index--; return obj; } // set和get也许用不上，但是你必须写上，这是规矩。你使用IDEA生成就行了。 // 封装：第一步：属性私有化，第二步：对外提供set和get方法。 public Object[] getElements() { return elements; } public void setElements(Object[] elements) { this.elements = elements; } public int getIndex() { return index; } public void setIndex(int index) { this.index = index; } }
数据结构（数组、链表、栈、队列、树）（二）：https://developer.aliyun.com/article/1416346
