一.鏈表帶哨兵
import java.util.Iterator;
import java.util.function.Consumer;
//帶哨兵
public class shuju02 implements Iterable<Integer> {//整體
private Node head=new Node(666,null);//頭指標
? @Override
? public Iterator<Integer> iterator() {
? //匿名內部類->帶名字的內部類
? return new NodeIterator();
? }
? private class NodeIterator implements Iterator<Integer> {
? Node p=head.next;
? @Override
? public boolean hasNext() {//是否有下一個元素
? return p!=null;//不慷訓傳真
? }
? @Override
? public Integer next() {//回傳當前值,并指向下一個元素
? int v=p.value;
? p=p.next;
? return v;
? }
? }
? private static class Node {
? int value;//值
? Node next;//下一個節點指標
? public Node(int value, Node next) {
? this.value = https://www.cnblogs.com/cgy-chen/archive/2023/07/12/value;
? this.next = next;
? }
? }
? public void addFirst(int value) throws IllegalAccessException {
? //1.鏈表為空
? // head=new Node(value,null);
? //2.鏈表非空(頭插)
? /* head = new Node(value, head);*/
? insert(0,value);
? }
? //遍歷鏈表
? //Params:consumer-要執行的操作
? public void loop(Consumer consumer) {
? Node p = head;
? while (p != null) {
? consumer.accept(p.value);
? p = p.next;
? }
? }
? //遍歷鏈表2
? //Params:consumer-要執行的操作
? public void loop2(Consumer consumer) {
? for (Node p = head; p != null; p = p.next){
? consumer.accept(p.value);
? }
? }
? //遍歷鏈表3(遞回遍歷)
? //Params:consumer-要執行的操作
? public void loop3(Consumerbefore,//沒有哨兵
? Consumerafter){
? recursion(head,before,after);
? }
? private void recursion(Node curr,//當前節點
? Consumerbefore,Consumerafter){//某個節點要進行的操作
? if(curr==null){
? return;
? }
? before.accept(curr.value);
? recursion(curr.next,before,after);//放前邊倒敘,放后面順序->指這句話
? after.accept(curr.value);
? }
? private Node findLast(){
? Node p;
? for(p=head;p.next!=null;p=p.next){
? }
? return p;
? }
? public void addLast(int value){
? Node last=findLast();
? last.next=new Node(value,null);
? }
/* public void test(){
? int i=0;
? for(Node p=head;p!=null;p=p.next,i++){
? System.out.println(p.value+"索引是:"+i);
? }
? 根據索引查找
Params:index-索引
Returns:找到，回傳該索引位置節點的值
Throws:IlLegalArgumentException-找不到，拋出index非法例外
}*/
? private Node findNode(int index){//給定索引位置
? int i=-1;
? for(Node p=head ;p!=null;p=p.next,i++){
? if(i==index){
? return p;
? }
? }
? return null;//沒找到
? }
? public int get(int index) throws IllegalAccessException {
? Node node=findNode(index);
? if(node==null){
? //拋例外
? illegalIndex(index);
? }
? return node.value;
? }
? //例外處理(重點)
? private static void illegalIndex(int index) throws IllegalAccessException {
? throw new IllegalAccessException(
? String.format("index[%d] 不合法%n", index)
? );
? }
? /*
向索引位置插入
*/
? public void insert(int index,int value) throws IllegalAccessException {
? Node prev=findNode(index-1);//找到上一個節點
? if(prev==null){
? illegalIndex(index);
? }
? prev.next=new Node(value,prev.next);
? }
? //1.問題
? //洗掉頭節點
? public void removeFirst() throws IllegalAccessException {
? remove(0);
? }
? public void remove(int index) throws IllegalAccessException {
? Node prev=findNode(index-1);//上一個節點
? if(prev==null){
? illegalIndex(index);
? }
? Node removed=prev.next;//被洗掉的節點
? if(removed==null){
? illegalIndex(index);
? }
? prev.next=removed.next;
? }
}
二.雙向鏈表帶哨兵
import java.util.Iterator;
//雙向鏈表,帶哨兵
public class shuju03 implements Iterable<Integer>{
static class Node{
Node prev;//上一個節點指標
int value;
Node next;//下一個節點指標
public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = https://www.cnblogs.com/cgy-chen/archive/2023/07/12/value;
this.next = next;
}
}
private Node head;//頭哨兵
private Node tail;//尾哨兵
public shuju03(){
head=new Node(null,666,null);
tail=new Node(null,666,null);
head.next=tail;
tail.prev=head;
}
private Node findNode(int index){
int i=-1;
for(Node p=head;p!=tail;p=p.next,i++){
if(i==index){
return p;
}
}
return null;
}
public void addFirst(int value) throws IllegalAccessException {
insert(0,value);
}
public void removeLast() throws IllegalAccessException {
Node removed=tail.prev;
if(removed==head){
illegalIndex(0);
}
Node prev=removed.prev;
prev.next=tail;
tail.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 insert(int index,int value) throws IllegalAccessException {
Node prev=findNode(index-1);
if(prev==null){
illegalIndex(index);
}
Node next=prev.next;
Node inserted=new Node(prev,value,next);
prev.next=inserted;
next.prev=inserted;
}
public void remove(int index) throws IllegalAccessException {
Node prev=findNode(index-1);
if(prev==null){
illegalIndex(index);
}
Node removed=prev.next;
if(removed==tail){
illegalIndex(index);
}
Node next=removed.next;
prev.next=next;
next.prev=prev;
}
private static void illegalIndex(int index) throws IllegalAccessException {
throw new IllegalAccessException(
String.format("index[%d] 不合法%n", index)
);
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node p=head.next;
@Override
public boolean hasNext() {
return p!=tail;
}
@Override
public Integer next() {
int value=https://www.cnblogs.com/cgy-chen/archive/2023/07/12/p.value;
return value;
}
};
}
}
三.雙向鏈表
import java.util.Iterator;
public class shuju04 implements Iterable<Integer> {
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node p=sentinel.next;
@Override
public boolean hasNext() {
return p!=sentinel;
}
@Override
public Integer next() {
int value= https://www.cnblogs.com/cgy-chen/archive/2023/07/12/p.value;
p=p.next;
return value;
}
};
}
/*
s->1->2->3->1->s
*/
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 shuju04(){
sentinel.prev=sentinel;
sentinel.next=sentinel;
}
//添加到第一個
//Params value-待添加值
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;
}
//添加到最后一個
//Params:value-待添加值
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("非法");
}
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("非法");
}
Node a=removed.prev;
Node b=sentinel;
a.next=b;
b.prev=a;
}
//根據值洗掉
// Params:value-目標值
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;
}
private Node findByValue(int value){
Node p=sentinel.next;
while(p!=sentinel){
if(p.value=https://www.cnblogs.com/cgy-chen/archive/2023/07/12/=value){
return p;
}
p=p.next;
}
return null;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/557143.html
標籤：其他
上一篇：量子糾纏：超越時空的連接
下一篇：返回列表