9.19单链表带哨兵和双向链表带哨兵

public class Main {
public static void main(String[] args) {
LNode L = new LNode();
L.addFirst(4);//头插
L.addFirst(3);
L.addFirst(2);
L.addFirst(1);
L.addLast(5);//尾插
L.Isempty();//判空
L.query();//遍历
System.out.println();
System.out.println(L.findLast().value);//最后一个结点
LNode.Node L2 = L.findNode(0);//指定索引查询
if (L2 == null) {
System.out.println("未查询到指定索引");
} else {
System.out.println(L2.value);
}
int i = L.valuecheck(1);
if (i == -1) {
System.out.println("不存在指定元素");
} else {
System.out.println("存在该元素，索引为" + i);
}
System.out.println("链表大小" + L.number());
L.removeIndex(0);
L.removeValue(2);
L.insertIndex(0, 2);
L.insertIndex(4, 6);
L.removeFirst();
L.removeLast();
L.query();

}

public static class LNode {
private Node head = new Node(-1, null);//头指针

public class Node {
int value;
Node next;

public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}

//头插
public void addFirst(int value) {
head.next = new Node(value, head.next);
/* insertIndex(0,value);*/
}

//尾插
public void addLast(int value) {
Node node = findLast();
node.next = new Node(value, null);
}

//头删
public void removeFirst() {
removeIndex(0);
}

//尾删
public void removeLast() {
removeIndex(number() - 1);
}

//查找指定节点
public Node findNode(int index) {
int i = -1;
for (Node p = head; p != null; p = p.next) {
if (i == index) {
return p;
}
i++;
}
return null;
}

//找最后一个节点
public Node findLast() {
Node p;
for (p = head; p.next != null; p = p.next) {
}
return p;
}

//遍历
public void query() {
for (Node p = head.next; p != null; p = p.next) {
System.out.print(p.value + " ");
}
}

//返回链表实际元素长度不含头结点
public int number() {
int i = 0;
for (Node p = head.next; p != null; p = p.next) {
i++;
}
return i;
}

//查找指定值所在索引
public int valuecheck(int value1) {
int i = -1;
for (Node p = head.next; p != null; p = p.next) {
i++;
if (p.value == value1) {
return i;
}
}
return -1;
}

//删除指定索引节点
public void removeIndex(int index) {
Node prev = findNode(index - 1);
if (prev == null) {
System.out.println("空链表");
return;
}
Node removed = prev.next;
if (removed == null) {
System.out.println("索引不存在");
return;
}
prev.next = removed.next;
}

//删除指定值节点
public void removeValue(int value1) {
int i = -1;
int j = 0;
for (Node p = head.next; p != null; p = p.next) {
i++;
if (value1 == p.value) {
j++;
removeIndex(i);
}
}
if (j == 0) {
System.out.println("该值不存在");
}
}

//按索引插入指定值
public void insertIndex(int index, int value) {
Node prev = findNode(index - 1);
if (prev == null) {
System.out.println("插入失败");
return;
}
prev.next = new Node(value, prev.next);
}

//判空
public void Isempty() {
if (head.next == null) {
System.out.println("空链表");
} else {
System.out.println("非空链表");
}
}

}
}