Java系列：常见数据结构(线性表，队列，栈，数组，树等)实现与API介绍（13）

1. 数据结构与算法

常见数据结构：集合，线性结构（线性表，队列，栈，数组，广义表），树，图，多维数组等。

2. 线性表

Java中,线性表对应着Collection中的List接口，而线性表的顺序存储结构则对应于ArrayList；

2.1 顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。

java定义一个简单的顺序表：

public class SeqList {
    
    /* 初始空间为10 */
    private static final int LIST_SIZE = 10;
    
    /* 数组data用来存放元素 */
    private int[] data;
    
    /* 当前表长，实际存储元素的个数 */
    private int length;
    
}

(1) Array

Array是固定大小的顺序表，定义为：

int[] arrA = new int[] {1,2,3,4,5};

(2) ArrayList

ArrayList是可以修改大小的顺序表。

调用 ArrayList API:

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

这是基于列表接口的可调整大小的数组的实现。实现所有列表List的操作，并允许所有类型的元素，包括null。除了实现List接口之外，这个类还提供了一些方法来操作内部用于存储列表的数组的大小。（这个类大致相当于Vector，只是它是不同步的。）

size、isEmpty、get、set、iterator和listIterator等方法操作是常数时间复杂度。add操作以摊余常量时间运行，即添加n个元素需要O（n）时间。所有其他操作都是在线性时间内运行的（粗略地说）。与LinkedList实现相比，常量因子（ constant factor）较低。

每个ArrayList实例都有一个容量。容量是用于存储列表中元素的数组的大小。它总是至少和列表大小一样大。当元素被添加到ArrayList时，它的容量会自动增长。除了增加一个元素具有固定的摊余时间成本这一事实外，增长策略的细节没有被指定。

应用程序在添加大量元素，增加ArrayList实例的容量之前，会使用ensureCapacity操作。这可能会减少容量重新分配的次数。

ensureCapacity(int minCapacity)

在增加ArrayList示例的容量时，为了确认它可以容纳指定最小的容量数目（minCapacity）的元素。

请注意，此实现不是同步的。如果多个线程同时访问一个ArrayList实例，并且至少有一个线程在结构上修改了列表，那么它必须在外部同步。（结构修改是指添加或删除一个或多个元素，或显式调整后备数组大小的任何操作；仅仅设置元素的值不是结构修改。）这通常是通过在自然封装列表的某个对象上同步来完成的。如果不存在这样的对象，则应该使用集合.synchronizedList方法。最好在创建时执行此操作，以防止意外的未同步访问列表：

   List list = Collections.synchronizedList(new ArrayList(...));

这个类的iterator和listIterator方法返回的迭代器是fail-fast的：如果在迭代器创建之后的任何时候，以任何方式（除了通过迭代器自己的remove或add方法）对列表进行结构修改，迭代器将抛出一个ConcurrentModificationException。

# 定义
ArrayList<String> slist = new ArrayList<String>();

# 添加元素
slist.add("hello");

# 删除元素
slist.remove("hello");

# 迭代
for(String item:slist){
	System.out.println(item);
}

2.2 链表

元素存储是离散的，通过逻辑上的指针连成一个整体。

java 定义一个简单的单链表：

并使用头插法，把新元素放到链表头部，来进行创建。

public class LinkList {

    /* 数据域 */
    private char data;

    /* 后继元素 */
    private LinkList next;

}

/**
 * 头插法创建表
 * @param chars 字符数组
 * @return 单链表
 */
public LinkList createListF(char[] chars) {

    LinkList node;
    LinkList head = null;

    for (char ch : chars) {
        /* 申请新节点 */
        node = new LinkList();
        node.data = ch;

        /* 指向后继节点 */
        node.next = head;
        head = node;
    }

    /* 返回头节点 */
    return head;

}

使用Java API LinkedList:

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

list和Deque接口的双链表实现。实现所有列表操作，并允许所有元素（包括null）。

请注意，此实现不是同步的。如果多个线程同时访问一个链接列表，并且至少有一个线程在结构上修改了该列表，则必须在外部同步该列表。（结构修改是添加或删除一个或多个元素的任何操作；仅仅设置元素的值不是结构修改。）这通常是通过在自然封装列表的某个对象上同步来完成的。如果不存在这样的对象，则应该使用集合.synchronizedList方法。最好在创建时执行此操作，以防止意外的未同步访问列表：

 List list = Collections.synchronizedList(new LinkedList(...));

同样，LinkedList 的 iterator 和 listIterator 方法都是 fail-fast。

# 定义链表
LinkedList<Integer> lklist = new LinkedList<Integer>();

# 添加元素
lklist.add(3);
lklist.addFirst(1);
lklist.addLast(999);

# 删除第一个元素
Integer firstvar = lklist.get(0);
lklist.remove();

# 删除并获得第一个元素(效果和 先 get(0),后remove()一样）
Integer firstvar2 = lklist.poll();

# 迭代
Iterator<Integer> listIter = lklist.iterator();
while(listIter.hasNext()){
	System.out.print(listIter.next()+" ");
}

Q:ArrayList 和 LinkedList的区别：

1、 ArrayList是实现了基于动态数组（内存连续）的数据结构，而LinkedList是基于链表的数据结构；

2、对于随机访问get和set，ArrayList要优于LinkedList，因为LinkedList要移动指针；

循环链表：

自己实现：

class Node {
 
    int value;
    Node nextNode;
 
    public Node(int value) {
        this.value = value;
    }
}

public class CircularLinkedList {
    private Node head = null;
    private Node tail = null;
 
    // ....
}

# 添加节点
public void addNode(int value) {
    Node newNode = new Node(value);
 
    if (head == null) {
        head = newNode;
    } else {
        tail.nextNode = newNode;
    }
 
    tail = newNode;
    tail.nextNode = head;
}
# 寻找元素
public boolean containsNode(int searchValue) {
    Node currentNode = head;
 
    if (head == null) {
        return false;
    } else {
        do {
            if (currentNode.value == searchValue) {
                return true;
            }
            currentNode = currentNode.nextNode;
        } while (currentNode != head);
        return false;
    }
}

双链表：

// Class for Doubly Linked List 
public class DLL { 
    Node head; // head of list 
  
    /* Doubly Linked list Node*/
    class Node { 
        int data; 
        Node prev; 
        Node next; 
  
        // Constructor to create a new node 
        // next and prev is by default initialized as null 
        Node(int d) { data = d; } 
    } 
} 

3. 栈

栈是先进后出，或者后进先出（LIFO）的数据结构。

调用 Java的 Stack API。

public class Stack<E>
extends Vector<E>

Deque接口及其实现提供了一组更完整和一致的后进先出堆栈操作，应该优先使用该类。例如：

   Deque<Integer> stack = new ArrayDeque<Integer>();

定义：

Stack<Integer> stack = new Stack<Integer>();
// push element on the top of stack
for(int i = 0; i < 5; i++) {
	stack.push(i);
}
// pop
for(int i = 0; i < 2; i++) {
	Integer y = (Integer) stack.pop();
	System.out.println(y);
}
// peek:see the top of the element of stack
System.out.println(stack.peek());

// pop all
while(!stack.isEmpty()) {
	Integer value = stack.pop();
	System.out.println(value);
}

Stack的其他方法：

（1）push

把item压入栈顶，和addElement(item)效果一致。

public E push(E item)

See Also:

Vector.addElement(E)

（2）pop
把栈顶的object进行移除，并且返回移除的那个object，如果栈为空，报错：EmptyStackException。

public E pop()

（3）peek

单纯查看栈顶的对象，如果栈是空，报错EmptyStackException。

public E peek()

（4）empty

查看栈是否为空。

（5）search

如果搜索的object出现在栈中，返回该对象距离栈顶的距离。

4. 队列

先进先出表（FIFO）。

此外，队列允许队头进行删除，队尾进行添加元素。LinkedList 实现了队列的接口。

上面已经介绍过了链表，

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

Queue<String> queue = new LinkedList<String>();
//添加元素
queue.add("hello");
queue.add("world");
queue.offer("!");
//递归
Iterator<String> queueIter = queue.iterator();
while(queueIter.hasNext()) {
	String name = queueIter.next();
	System.out.println(name);
}
// 方法二
for(String str:queue) {
	System.out.println(str);
}
//删除元素
queue.remove("how");
//查看队列头部的元素
System.out.println(queue.peek());

注意，add()和remove()方法在失败的时候会抛出异常(不推荐)，添加可以用offer(),删除用poll()，这两个操作再队列已满或为空时，不会抛出异常，但分别会返回 false 和 \null .

LinkedList 还有其他的方法：

（1）getFirst

返回列表的第一个元素,如果列表为空，报错：NoSuchElementException

public E getFirst()

（2）getLast

返回列表的最后一个元素。如果列表为空，报错：NoSuchElementException .

public E getLast()

（3）removeFirst

移除并返回列表的第一个元素。

public E removeFirst()

（4）removeLast

移除和返回列表的最后一个元素。

public E removeLast()

（5）addFirst

把元素插入到列表的开始位置。

public void addFirst(E e)

（6）addLast

把元素插入到列表的最后位置。

public void addLast(E e)

（7）contains

判断列表是否包含特定的元素，如果有，返回true;

public boolean contains(Object o)

判断的条件：

o==null ? e==null : o.equals(e)

（8）size

判断列表包含元素的数目。

public int size()

（9）add

把元素添加到元素的最后位置。

public boolean add(E e)

方法等同于 addLast(E).

（10）remove

把第一个出现的指定元素进行移除，并且返回true。如果不包含指定元素，列表不变。

o==null ? get(i)==null : o.equals(get(i))

（11）addAll

把特定collection的所有元素添加到列表的最后。如果指定的待添加的collection是null，报错NullPointerException 。

public boolean addAll(Collection<? extends E> c)

（12）clear

把列表的所有元素进行移除。

public void clear()

（13）get

返回特定索引下的元素。

public E get(int index)

（14）set

替换原来索引位置的元素成指定的元素。

public E set(int index,
    E element)

(15) add

public void add(int index,
       E element)

还有一些方法可以去官网看看。

6. 集合

主要介绍没有逻辑规律的Set，包括 HashSet, TreeSet.

HashSet

HashSet的底层是哈希表。

public static void main(String[] args) {  
    HashSet set=new HashSet();  
    set.add(new Person("a1", 12));   
      
    System.out.println(set.contains(new Person("a2", 34)));  
    System.out.println(set.remove(new Person("a2", 34)));  
      
    Iterator it=set.iterator();  
    while (it.hasNext()) {  
        Person p=(Person)it.next();  
        System.out.println(p.getName()+"的年龄是"+p.getAge());        
    }  
}

TreeSet

TresSet:可以对集合中的元素排序。底层数据结构是二叉树.

TreeSet ts=new TreeSet();  

7. 树

树由父节点，子节点组成。树可以分为二叉树，平衡二叉树，红黑树，B树等。
定义树：

public class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) {val = x;}
}

8. 图

图有节点和边组成，实现的方式有：

Map<Integer, List<int[]>> graph = new HashMap();

图和树的区别在于，图可能会出现环的情况。

图的算法题LeetCode network delay time.

---

参考：

1. 数据结构与算法 ---- 线性表 及Java实现 顺序表、链表、栈、队列;
2. 线性表及其算法（java实现）;
3. beginnersbook Java array list;
4. beginnersbook Java Linked list;
5. beginnersbook Java circular linked list 实现；
6. geeksforgeeks doubly linked list;
7. 菜鸟教程 Java栈的实现；
8. Java queue examples;
9. Java queue 实例;
10. 个人博客 数据结构：数组、链表、堆栈、队列 ;
11. 个人博客 Java集合set;
12. 个人博客 二叉树;
13. Oracle docs, Class ArrayList;