数据结构算法（一）之线性表
2018-06-25 本文已影响23人
innovatorCL
一、引言
java.util 包中三个重要的接口及特点：List（列表）、Set（保证集合中元素唯一）、Map（维护多个key-value键值对，保证key唯一）。其不同子类的实现各有差异，如是否同步（线程安全）、是否有序。
二、List 线性表/列表
线性表按照存储结构可以分为顺序存储结构和链式存储结构。其中顺序存储结构在 java 的表现就是 ArrayList（本质就是一个数组），链式存储结构表现为 LinkedList。
1.线性表的顺序存储结构：ArrayList
ArrayList、Vector 是线性表，使用 Object 数组作为容器去存储数据的，容量可以动态增长。区别是 ArrayList 是非同步的，Vector 是同步的。不用考虑多线程时应使用 ArrayList 来提升效率。
-
ArrayList 的构造方法
ArrayList 提供了三个构造方法，可以构造一个默认初始容量为 12 (Android 为 12，Java 为 10) 的空列表和构造一个指定初始容量的空列表以及构造一个包含指定 collection 的元素的列表，这些元素按照该集合的迭代器返回它们的顺序排列。
public class ArrayList<E> extends AbstractList<E> implements Cloneable, Serializable, RandomAccess {
/**
* 最小容量值，Java 中为 10，Android 中为 12
*/
private static final int MIN_CAPACITY_INCREMENT = 12;
/**
* 数组元素的长度
*/
int size;
/**
* ArrayList 是基于数组的方式实现的
*/
transient Object[] array;
/**
* 创建一个指定带容量大小的 ArrayList
*/
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity < 0: " + capacity);
}
array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}
/**
* 创建一个无参构造的 ArrayList
*/
public ArrayList() {
array = EmptyArray.OBJECT;
}
/**
* 创建一个包含 collection 的 ArrayList
*/
public ArrayList(Collection<? extends E> collection) {// Java 的多态性
if (collection == null) {
throw new NullPointerException("collection == null");
}
Object[] a = collection.toArray();
if (a.getClass() != Object[].class) {
Object[] newArray = new Object[a.length];
System.arraycopy(a, 0, newArray, 0, a.length);
a = newArray;
}
array = a;
size = a.length;
}
-
ArrayList 的添加方法
ArrayList 提供了很多个添加元素的方法，我们看看如何在末位添加，在指定位置添加以及添加一个集合。
/**
* 添加方法，添加到列表的尾部
*/
@Override
public boolean add(E object) {
Object[] a = array;// 将array赋值给一个局部数组
int s = size;// 用局部的s获取长度
if (s == a.length) {// 如果现在的长度等于数组array的长度，那么空间满了，需要声明一个新数组
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];// s<6?12:6
System.arraycopy(a, 0, newArray, 0, s);// 把原来的数组拷贝到新的数组中来
array = a = newArray;
}
a[s] = object;// 把元素添加进来
size = s + 1;// 长度+1
modCount++;// 计量器，只要数组中元素动一下，它就+1
return true;
}
/**
* 添加方法，添加到指定位置
*
* @param index the index at which to insert the object.
* @param object the object to add.
* @throws IndexOutOfBoundsException when {@code location < 0 || location > size()}
*/
@Override public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
// 当数组长度容量足够时，执行System.arraycopy方法实现数组的复制
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {// 当数组容量不足时，进行扩容
// assert s == a.length;
// 创建新数组
Object[] newArray = new Object[newCapacity(s)];
// 将数据拷贝到新数组中，并移动位置
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
modCount++;
}
/**
* 添加方法，将容器中所有元素添加到此列表的尾部
* Adds the objects in the specified collection to this {@code ArrayList}.
* @param collection the collection of objects.
* @return {@code true} if this {@code ArrayList} is modified, {@code false}
* otherwise.
*/
@Override public boolean addAll(Collection<? extends E> collection) {
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int s = size;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize > a.length) {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, s, newPartSize);
size = newSize;
modCount++;
return true;
}
-
ArrayList 的删除方法
ArrayList 提供了 很多个删除的方法，我们看看如何删除指定位置的元素或者删除首次出现的某个元素。
/**
* 删除列表中指定位置上的元素
* @param index the index of the object to remove.
* @return the removed object.
* @throws IndexOutOfBoundsException when {@code location < 0 || location >= size()}
*/
@Override public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
// 将删除位置之后的元素向前挪动一个位置
System.arraycopy(a, index + 1, a, index, --s - index);
// 将数组末尾置空
a[s] = null;
size = s;
modCount++;
return result;
}
// 删除列表中首次出现的指定元素（如果存在）
@Override public boolean remove(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
}
return false;
}
注意啦啦啦！！！
System.arraycopy() 是 native 方法。
/**
* Copies {@code length} elements from the array {@code src},
* starting at offset {@code srcPos}, into the array {@code dst},
* starting at offset {@code dstPos}.
*
* <p>The source and destination arrays can be the same array,
* in which case copying is performed as if the source elements
* are first copied into a temporary array and then into the
* destination array.
*
* @param src
* the source array to copy the content.
* @param srcPos
* the starting index of the content in {@code src}.
* @param dst
* the destination array to copy the data into.
* @param dstPos
* the starting index for the copied content in {@code dst}.
* @param length
* the number of elements to be copied.
*/
public static native void arraycopy(Object src, int srcPos,
Object dst, int dstPos, int length);
结论：ArrayList 是基于数组实现的，是一个动态数组，初始容量 Java 为10，Android 为12。其容量能自动增长，增长默认的长度的 1/2。我们可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，因此插入删除元素的效率低，其实所有操作就是对数组的操作。
2.线性表的链式存储结构：LinkedList
LinkedList 是双向链表，链表随机位置插入、删除数据时比线性表快，遍历比线性表慢。
LinkedList 双向链表
- 链式存储结构的优缺点：
优：删除和插入效率高
缺：查询效率低
-
LinkedList 的构造方法
LinkedList 提供了两个构造方法，可以构造一个只有头结点的空链表和一个包含指定 collection 的元素的链表，这些元素按照该集合的迭代器返回它们的顺序排列。
public class LinkedList<E> extends AbstractSequentialList<E> implements
List<E>, Deque<E>, Queue<E>, Cloneable, Serializable {
private static final long serialVersionUID = 876323262645176354L;
transient int size = 0;
transient Link<E> voidLink;// 头指针
/**
* 内部精简后的静态 Link 类，这个其实就是一个结点
*/
private static final class Link<ET> {
ET data;
Link<ET> previous, next;// 双向链表
Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
/**
* LinkedList 无参构造
*/
public LinkedList() {
// 实例化头指针
voidLink = new Link<E>(null, null, null);
// 分别让头指针的 previous 和 next 等于头指针
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
/**
* 接收一个 Collection 参数的 LinkedList 构造方法
*/
public LinkedList(Collection<? extends E> collection) {
this();
addAll(collection);
}
-
LinkedList 的添加方法
LinkedList 提供了很多个添加方法，我们看看如何在指定位置添加一个元素以及在末尾添加元素。
/**
* 添加方法，在指定位置进行添加
* @param location the index at which to insert.
* @param object the object to add.
* @throws IndexOutOfBoundsException if {@code location < 0 || location > size()}
*/
@Override
public void add(int location, E object) {
if (location >= 0 && location <= size) {// 在链表的中间添加
Link<E> link = voidLink;
// 为了提高效率，采用二分法的思想，需要判断前半段和后半段进行插入
if (location < (size / 2)) {// 表示在前半段
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {// 表示在后半段
for (int i = size; i > location; i--) {
link = link.previous;
}
}
// 将当前结点的前一结点赋值给 previous
Link<E> previous = link.previous;
// 初始化先创建结点 newLink，其数据域是 object，前面的结点是 previous，后面的结点是 link
Link<E> newLink = new Link<E>(object, previous, link);
// 让 previous.next 指向新节点
previous.next = newLink;
// 同时让 link.previous 指向新节点
link.previous = newLink;
size++;// 长度+1
modCount++;// 计量器+1
} else {
throw new IndexOutOfBoundsException();
}
}
/**
* 将元素 (E) 添加到 LinkedList 中
* @param object the object to add.
* @return always true
*/
@Override
public boolean add(E object) {
return addLastImpl(object);
}
/**
* 在最后添加元素的方法
*/
private boolean addLastImpl(E object) {
// 将头结点的 previous，其实就是头结点自己，赋值给 oldLast
Link<E> oldLast = voidLink.previous;
// 新建一个要插入的新节点，其数据域是 object，previous 结点是 oldLast，next 结点是 voidLink（头结点）
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
// 让头指针的前面 previous 指向新建结点
voidLink.previous = newLink;
// 让oldLast.next 指向新建结点
oldLast.next = newLink;
size++;// 长度+1
modCount++;// 计量器+1
return true;
}
-
LinkedList 的删除方法
LinkedList 提供了很多个删除方法，我们看看如何在指定位置删除元素。
/**
* Removes the object at the specified location from this {@code LinkedList}.
* @param location the index of the object to remove
* @return the removed object
* @throws IndexOutOfBoundsException
* if {@code location < 0 || location >= size()}
*/
@Override
public E remove(int location) {
// 先判断 location >= 0 && location < size
if (location >= 0 && location < size) {
Link<E> link = voidLink;
// 采用二分法的思想，先找前半段
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {// 再找后半段
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;// 待删除结点的前一结点的后指针指向待删除结点的后一个结点
next.previous = previous;// 待删除结点的后一结点的前指针指向待删除结点的前一个结点
size--;// 长度-1
modCount++;// 计量器+1
// 返回移除结点的内容
return link.data;
}
throw new IndexOutOfBoundsException();
}
结论：LinkedList 在添加和删除元素的时候会通过二分法判断应该从哪里查找会比较快找到要插入/删除的位置，然后进行指针修改，这个就比 ArrayList 插入/删除的效率高很多。
三、Java 实现单链表的反转
对于单链表的反转，我们可以使用递归法或者遍历的方法。
- 简单的 Java 单链表节点类
public class Node {
private int data;// 数据域
private Node next;// 指针域
public Node(int d) {
this.data = d;
}
public int getData() {
return data;
}
public void setData(int d) {
this.data = d;
}
public Node getNext() {
return next;
}
public void setNext(Node Next) {
this.next = Next;
}
}
-
递归的方法
递归的思路其实就是从尾节点开始反转，然后一直递归到头结点。
public class Test {
public static void main(String[] args){
Node head = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
head.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
// 打印反转前的链表
Node h = head;
while (null != h) {
System.out.print(h.getData() + " ");
h = h.getNext();
}
// 调用反转方法
head = reverseByDiGui(head);
System.out.println("\n**************************");
// 打印反转后的结果
while (null != head) {
System.out.print(head.getData() + " ");
head = head.getNext();
}
}
/**
* 递归，在反转当前节点之前先反转后续节点
*/
public static Node reverseByDiGui(Node head){
if (head == null || head.getNext() == null) {
return head;// 空链或者已传递到尾结点
}
Node reHead = reverseByDiGui(head.getNext());//head.getNext()会将当前节点传递到最后，reHead会一直保持在尾节点
//注意这里的形参 head 是断点保护现场的变量，指向的是每次遍历的那个节点
//比如第一次遍历的时候指 head'，第二次就指 head''，都是不同的引用来的
head.getNext().setNext(head);// 将当前结点的指针域指向前一结点
head.setNext(null);// 前一结点的指针域令为null;
return reHead;// 反转后新链表的头结点
}
}
结果
递归实现单链表反转
-
遍历的方法
遍历的思路其实就是从头节点开始反转，需要用 current、pre、next 三个指针辅助记录当前节点，当前节点的前节点，当前节点的后节点。一个一个节点地反转，直到最后那一个。
public static Node reverseByBianLi(Node head){
//头结点
Node pre = head;
//有实际内容的节点
Node cur = head.getNext();
//保存下一节点的临时变量
Node temp;
//空链表
if(cur == null){
return head;
}
while(cur != null){
//先保存下一节点，再改当前节点
temp = cur.getNext();
//更改当前节点的指向
cur.setNext(pre);
//指针传递下去
pre = cur;
cur = temp;
}
//原来的头结点的下一个节点指向null
head.setNext(null);
return pre;
}
结果
遍历实现单链表反转
四、判断是否为回字链
题目：请检查一个链表是否为回文链表。在 O(n) 的时间和 O(1) 的额外空间中做到。
思路：链表用到了快慢指针，快指针每次跳两下，慢指针每次跳一下，这样快指针到终点的时候慢指针刚好一半，然后反转后半部分链表进行对比。该方法时间复杂度O(n)、空间复杂度O(1)。
public class Solution {
public static boolean isPalindrone(Node head) {
//单节点直接返回 true
if(head == null || head.next == null) {
return true;
}
Node fast = head;
Node slow = head;
Node pre = head;
//找到回文链表的中点
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//此时，fast 正好走到链表的末尾，反转中点到末尾的这段链表，然后比对
Node last = slow.next;
//last 作为当前节点，slow 作为当前节点的前节点，temp 作为当前节点的后节点
while(last.next != null) {
Node temp = last.next;
last.next = temp.next;
temp.next = slow.next;
slow.next = temp;
}
//slow 一直都处于中点，开始遍历进行比对
while(slow.next != null) {
slow = slow.next;
if(pre.data != slow.data) {
return false;
}
pre = pre.next;
}
return true;
}
}
