1、基本介绍
2、应用实例（双向链表）
package linkedlist;import java.util.Scanner;public class DoubleLinkedList {public static void main(String[] args) {LinkedNode head = new LinkedNode(0);Scanner scanner = new Scanner(System.in);boolean loop = true;char op;int pos;int val;while(loop) {System.out.println("\\n链表插入~(i)");System.out.println("链表删除~(d)");System.out.println("链表修改~(u)");System.out.println("链表打印~(p)");System.out.println("反向打印~(r)");System.out.println("链表插入指定位置~(c)");System.out.println("链表删除指定位置~(s)");System.out.println("链表有效节点个数~(n)");System.out.println("链表倒数第k个节点~(g)");System.out.println("退出程序(q)~");System.out.print("请选择你要执行的操作：");op = scanner.next().charAt(0);switch (op) {case 'i':System.out.print("请输入要插入的值：");val = scanner.nextInt();insert(head, val);break;case 'd':delete(head);break;case 'u':System.out.print("请输入要更新的值：");val = scanner.nextInt();System.out.print("请输入元素的位置：");pos =scanner.nextInt();update(head, pos, val);break;case 'p':System.out.print("单链表元素：");print(head);break;case 'r':System.out.print("单链表元素(反向遍历)：");reversePrint(head);break;case 'c':System.out.print("请输入要插入的值：");val = scanner.nextInt();System.out.print("请输入元素的位置：");pos =scanner.nextInt();insertByPosition(head, val, pos);break;case 's':System.out.print("请输入元素的位置：");pos =scanner.nextInt();deleteByPosition(head, pos);break;case 'n':count(head);break;case 'g':System.out.print("请输入k的值：");pos =scanner.nextInt();get(head, pos);break;default:scanner.close();loop = false;break;}}}public static void insert(LinkedNode head, int insertVal) {LinkedNode node = new LinkedNode(insertVal);LinkedNode temp = head;if (head.next == null) {head.next = node;node.pre = head;System.out.println("结点插入成功~");} else {while (temp.next != null) {temp = temp.next;}temp.next = node;node.pre = temp;System.out.println("结点插入成功~");}}public static void delete(LinkedNode head) {if (isEmpty(head)) {throw new RuntimeException("单链表没东西啦~");}LinkedNode temp = head.next; // temp：被删除节点int deleteVal = temp.data;temp.pre.next = temp.next;temp.next.pre = temp.pre;System.out.println("结点删除成功~");System.out.println("删除结点元素值：" + deleteVal);}public static void update(LinkedNode head, int pos, int updateVal) {LinkedNode temp = head;int count = 0;while (temp.next != null && count < pos) {count++;temp = temp.next;}if (temp != null) {temp.data = updateVal;} else {throw new RuntimeException("该元素不存在~");}}public static void print(LinkedNode head) {if (isEmpty(head)) {throw new RuntimeException("单链表没东西~");}LinkedNode temp = head.next;while (temp != null) {System.out.print(temp.data+ " ");temp = temp.next;}System.out.println();}private static void reversePrint(LinkedNode head) {if (isEmpty(head)) {throw new RuntimeException("单链表没东西~");}LinkedNode temp = head;while(temp.next != null) {temp = temp.next;}while (temp != head) {System.out.print(temp.data + " ");temp = temp.pre;}System.out.println();}public static void insertByPosition(LinkedNode head, int insertVal, int pos) {LinkedNode temp = head;LinkedNode node = new LinkedNode(insertVal);int count = 0;while (temp.next != null && count < pos - 1) {count++;temp = temp.next;}node.next = temp.next; // temp指向的是插入位置的前一个位置temp.next.pre = node;temp.next = node;node.pre = temp;}public static void deleteByPosition(LinkedNode head, int pos) {LinkedNode temp = head;int count = 0;while (temp.next != null && count < pos) {count++;temp = temp.next;}temp.pre.next = temp.next; // temp：指向的是被删节点temp.next.pre = temp.pre;}private static int count(LinkedNode head) {if (isEmpty(head)) {throw new RuntimeException("链表没东西，臣妾很难做到啊~");}LinkedNode temp = head;int count = 0;while (temp.next != null) {temp = temp.next;count++;}System.out.println("链表有效节点个数：" + count);return count;}private static void get(LinkedNode head, int index) {if (isEmpty(head)) {throw new RuntimeException("链表没东西，臣妾很难做到啊~");}// 1、获取链表长度int size = count(head);// 2、边界判断if (index <= 0 || index > size) {System.out.println("越界了~朋友");}// 3、遍历到size-index位置，就是倒数第k个节点LinkedNode temp = head.next;for (int i = 0; i < size-index; i++) {temp = temp.next;}System.out.println("倒数第"+ index + "个节点的值：" + temp.data);}public static boolean isEmpty(LinkedNode head) {if (head.next == null) {return true;}return false;}
}class LinkedNode{public int data;public LinkedNode pre;public LinkedNode next;public LinkedNode(int data) {this.data = data;this.next = null;}
}
