1.为什么用dummyHead虚拟头结点
对于add操作我们addFirst 总是和其他地方不一样，因为头结点是没有前一个结点的，因此我们要浪费一个空间使其为dummyHead这样链表总是以nul作为头结点
/**
* 内部类node，只有这个类可以访问到,用户不需要知道链表内部结构，
* 也可以做成外部类
*/
private class Node{
public E e;
/**
* 指针 指向下一个节点
*/
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循环为什么循环到index - 1
- 这是因为我们有虚拟头结点，所以当index为0时候我们不需要循环，prev就是dummyhead 然后进行add操作
- 如果index 为1的时候我们需要循环到0处....2时循环到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）方法很简单 我们从虚拟头结点出发，每次指向的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的垃圾回收即可
