dsa_linkedlist
在两家公司面试时被均被考核到链表，具体问题如下：
- 链表和顺序表有什么区别？
- 给定一个链表如何判断是循环链表？
因为面的是测试岗，所以要求不高。
对于问题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;
}
}
