目录
//单向链表类
public class LinkedList {
//头指针
private Node head=null;
private static class Node{
int value;
Node next;
public Node(int value,Node next){
this.value=value;
this.next=next;
}
}
}
//头部添加元素
public void addFirst(int value){
head=new Node(value,head);
}
//找到链表中的最后一个节点
public Node findLast(){
if(head==null){
return null;
//空链表
}
Node p;
for(p=head;p.next!=null;p=p.next){
}
return p;
}
//向链表尾部添加元素
public void addLast(int value){
Node last=findLast();
if(last==null){
addFirst(value);
return;
}
last.next=new Node(value,null);
}
//遍历链表
public void loop(){
Node p=head;
while(p!=null){
System.out.print(p.value+" ");
p=p.next;
}
System.out.println();
}
获取指定索引的节点的value值。
这里注意一下findNode方法是获取指定索引处的节点,所以需要一个计量器i,让这个i=0开始,为什么呢?因为head其实就是第一个节点,后面双向链表计量i是=-1开始的,但是双向链表中的head并不是第一个节点,它的next才是第一个节点,所以一定要特别注意单向链表中的head与双向链表的head的区别(个人看法)
//找到指定索引处的节点 public Node findNode(int index){ int i=0; for(Node p=head;p.next!=null;p=p.next,i++){ if(i==index){ return p; } } return null;//没有找到该节点 } //获取指定索引处的节点的值(value) public int get(int index){ Node p=findNode(index); if(p==null){ throw new IllegalArgumentException(String.format("index[%d]不合法",index)); } return p.value; }
//向索引位置插入 public void insert(int index,int value){ if(index==0){ addFirst(value); } //找到上一个节点 Node prev=findNode(index-1); if(prev==null){ throw new IllegalArgumentException(String.format("index[$d]不合法",index)); } prev.next=new Node(value,prev.next); }
//删除第一个节点
public void removeFirst(){
if(head==null){
throw new IllegalArgumentException(String.format("index[0]不合法"));
}
head=head.next;
}
//删除指定索引处的节点 public void remove(int index){ if(index==0){ removeFirst(); return; } Node prev=findNode(index-1);//上一个节点 if(prev==null){ throw new IllegalArgumentException(String.format("索引异常")); } Node removed=prev.next;//被删除的节点 if(removed==null){ throw new IllegalArgumentException(String.format("索引异常")); } prev.next=removed.next; }
//双向链表类
public class DoubleLinkedList {
private Node head;
private Node tail;
private static class Node{
Node prev;
int value;
Node next;
public Node(Node prev,int value,Node next){
this.prev=prev;
this.value=value;
this.next=next;
}
}
//初始化
public DoubleLinkedList(){
head=new Node(null,100,null);
tail=new Node(null,999,null);
head.next=tail;
tail.prev=head;
}
}
在指定索引处添加
//找到指定索引处的节点 private Node findNode(int index){ int i=-1; for(Node p=head;p!=tail;i++,p=p.next){ if(i==index){ return p; } } return null; } //向指定位置添加节点 public void insert(int index,int value){ Node prev=findNode(index-1); if(prev==null){ throw new IllegalArgumentException(String.format("索引异常")); } Node next=prev.next; Node inserted=new Node(prev,value,next); prev.next=inserted; next.prev=inserted; }
删除指定索引处的节点
//删除指定索引处的节点 public void remove(int index){ Node prev=findNode(index-1); if(prev==null){ throw new IllegalArgumentException(String.format("索引异常")); } Node removed=prev.next; //如果删除的元素是尾哨兵 if(removed==tail){ throw new IllegalArgumentException(String.format("索引异常")); } Node next=removed.next; prev.next=next; next.prev=prev; }
?向尾部添加节点
//向尾部添加元素 public void addLast(int value){ Node last=tail.prev; Node added=new Node(last,value,tail); last.next=added; tail.prev=added; }
//删除最后一个节点 public void removeLast(){ Node removed=tail.prev; if(removed==head){ throw new IllegalArgumentException(String.format("索引异常")); } Node prev=removed.prev; prev.next=tail; tail.prev=prev; }
?双向环形链表(我这里说的是有哨兵节点的)不同的地方在于,尾结点的next指向了哨兵节点,哨兵节点的next指向的是第一个节点,哨兵节点的prev指向的是尾节点。
//双向环形链表
//注意是有哨兵节点sentinel
//sentinel.next是第一个节点,sentinel.prev是最后一个节点
public class DoubleSentinelList {
private static class Node{
Node prev;
int value;
Node next;
public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
private Node sentinel=new Node(null,-1,null);//哨兵节点
//初始化
public DoubleSentinelList(){
sentinel.next=sentinel;
sentinel.prev=sentinel;
}
}
//向首部添加 public void addFirst(int value){ Node a=sentinel; Node b=sentinel.next; Node added=new Node(a,value,b); a.next=added; b.prev=added; } //向尾部添加 public void addLast(int value){ Node a=sentinel.prev; Node b=sentinel; Node added=new Node(a,value,b); a.next=added; b.prev=added; }
//删除首部 public void removeFirst(){ Node removed=sentinel.next; if(removed==sentinel){ throw new IllegalArgumentException(String.format("非法")); } Node a=sentinel; Node b=removed.next; a.next=b; b.prev=a; } //删除尾部 public void removeLast(){ Node removed=sentinel.prev; if(removed==sentinel){ throw new IllegalArgumentException(String.format("非法")); } Node a=removed.prev; Node b=sentinel; a.next=b; b.prev=a; }
//根据值寻找对应的节点 public Node findByValue(int value){ Node p=sentinel.next; while(p!=sentinel){ if(p.value==value){ return p; } p=p.next; } return null; } //根据值删除对应的节点 public void removeByValue(int value){ Node removed=findByValue(value); if(removed==null){ return;//不用删除,因为没找到 } Node a=removed.prev; Node b=removed.next; a.next=b; b.prev=a; }
?