1.為什么用dummyHead虛擬頭結點
對于add操作我們addFirst 總是和其他地方不一樣晚缩，因為頭結點是沒有前一個結點的，因此我們要浪費一個空間使其為dummyHead這樣鏈表總是以nul作為頭結點
/**
* 內(nèi)部類node呀闻，只有這個類可以訪問到,用戶不需要知道鏈表內(nèi)部結構，
* 也可以做成外部類
*/
private class Node{
public E e;
/**
* 指針 指向下一個節(jié)點
*/
public Node next;
public Node(E e,Node next){
this.e = e;
this.next = next;
}
public Node(E e){
this(e,null);
}
public Node(){
this(null,null);
}
@Override
public String toString(){
return e.toString();
}
}
2.我們可以對鏈表初始化
//我們將第一個元素作為虛擬頭結點
private Node dummyHead;
private int size;
public LinkedList(){
dummyHead = new Node(null, null);
size = 0;
}
3.添加元素
public void add(int index, E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("error index");
}
Node prev = dummyHead ;
//從第一個到要找的鏈表前面一個
for(int i = 0; i <index; i++){
prev = prev.next;
}
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
}
public void addLast(E e){
add(size,e);
}
public void addFirst(E e){
add(0, e);
}
這里我們主要add方法中的for循環(huán)為什么循環(huán)到index - 1
- 這是因為我們有虛擬頭結點，所以當index為0時候我們不需要循環(huán)傀履，prev就是dummyhead 然后進行add操作
- 如果index 為1的時候我們需要循環(huán)到0處....2時循環(huán)到1處.....這樣每一個prev都是index前的一個結點
- 同樣有個虛擬頭結點 get操作也很簡單
4.get
public E get(int index){
if(index < 0 || index > size){
throw new IllegalArgumentException("error index");
}
Node cur = dummyHead.next;
for(int i = 0 ; i < index; i++){
cur = cur.next;
}
return cur.e;
}
get（index）方法很簡單 我們從虛擬頭結點出發(fā)，每次指向的next正好是index處的位置莉炉，因此到index - 1處 cur.next剛好的是需要的元素我們只要 cur = cur.next;即可钓账，同理得first和last很簡單啦
public E getFirst(){
return get(0);
}
public E getLast(){
return get(size);
}
5.檢查是否包含
public boolean contains(E e){
Node cur = dummyHead.next;
while (cur!= null){
if(cur.e.equals(e)){
return true;
}
cur = cur.next;
}
return false;
}
6.鏈表的刪除
思路很簡單 只要找到prev 然后將prev.next = delNode.next 然后delNode.next =null 方便JAVA的垃圾回收即可
