dsa_linkedlist
在兩家公司面試時被均被考核到鏈表廊佩，具體問題如下：
- 鏈表和順序表有什么區(qū)別？
- 給定一個鏈表如何判斷是循環(huán)鏈表靖榕？
因為面的是測試崗标锄，所以要求不高。
對于問題1茁计，參考 stackoverflow 的回答：
stackoverflow:When to use LinkedList over ArrayList?
針對其中的部分描述料皇，編寫了測試代碼進行驗證：
package testing.interview;
import java.util.ArrayList;
import java.util.Date;
import java.util.LinkedList;
/**
* Print the time of linkedList and arrayList by add element 100000 times.
*
* @author lishoujun https://github.com/lishoujun/java-learn
*/
public class LinkedListAdd {
public static void main(String[] args) {
final int size = 100000;
LinkedList<Integer> linkedList = new LinkedList<>();
long linkedListAddStartTime = new Date().getTime();
System.out.println(linkedListAddStartTime);
for (int i = 0; i < size; i++) {
linkedList.add(0, i);
}
long linkedListAddEndTime = new Date().getTime();
System.out.println("linkedListTime:" + (linkedListAddEndTime - linkedListAddStartTime));
ArrayList<Integer> arrayList = new ArrayList<>();
long arrayListStartTime = new Date().getTime();
for (int i = 0; i < size; i++) {
arrayList.add(0, i);
}
long arrayListEndTime = new Date().getTime();
System.out.println("arrayListTime:" + (arrayListEndTime - arrayListStartTime));
// for debug
try {
Thread.sleep(100000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
對于問題2
package testing.interview;
/**
* A hasCycle function to check is there a Cycle in LinkedList.
* the LinkedList is a simple edition just has an int data and a Node as next.
*
* @author lishoujun https://github.com/lishoujun/java-learn
*/
public class LinkedListCycle {
public static void main(String[] args) {
System.out.println(hasCycle(null));
System.out.println(hasCycle(new Node(1, null)));
System.out.println(hasCycle(new Node(1, new Node(1, null))));
Node first = new Node(1, null);
first.next = first;
System.out.println(hasCycle(first));
Node second = new Node(1, first);
first.next = second;
System.out.println(hasCycle(first));
/**
* result:
* false
* false
* false
* true
* true
*/
}
public static boolean hasCycle(Node start) {
if (start == null || start.next == null)
return false;
Node tmp = start;
Node current = start.next;
while (current.next != null) {
if (tmp == current) {
return true;
}
current = current.next;
}
return false;
}
}
class Node {
int data;
Node next;
Node() {
}
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
