代码实现

  1. package com.xiaoxuanfeng.dataStructure;
  3. // 链表
  4. public class Day4_Linked {
  5.     // 链表节点
  6.     public static class Node {
  7.         int data;
  8.         Node next;
  10.         public Node(int data) {
  11.             this.data = data;
  12.         }
  13.     }
  15.     // 头节点指针
  16.     private static Node head;
  17.     // 尾节点指针
  18.     private static Node last;
  19.     // 链表实际长度
  20.     private static int size;
  22.     // 插入操作 data: 插入的元素 index: 插入的位置
  23.     public void insert(int data, int index) {
  24.         if (index < 0 || index > size) {
  25.             throw new IndexOutOfBoundsException("下标越界");
  26.         }
  27.         Node insertNode = new Node(data);
  28.         if (size == 0) { // 空链表
  29.             head = insertNode;
  30.             last = insertNode;
  31.         } else if (index == 0) { // 插入头部
  32.             insertNode.next = head;
  33.             head = insertNode;
  34.         } else if (size == index) { // 插入尾部
  35.             last.next = insertNode;
  36.             last = insertNode;
  37.         } else { // 插入中间
  38.             Node prevNode = getNode(index - 1);
  39.             insertNode.next = prevNode.next;
  40.             prevNode.next = insertNode;
  41.         }
  42.         size++;
  43.     }
  45.     // 删除操作 index: 删除的位置
  46.     public static Node remove(int index) {
  47.         if (index < 0 || index > size) {
  48.             throw new IndexOutOfBoundsException("数组越界");
  49.         }
  50.         Node removeNode = null;
  51.         if (index == 0) { // 删除头节点
  52.             removeNode = head;
  53.             head = head.next;
  54.         } else if (index == size - 1) { // 删除尾节点
  55.             Node prevNode = getNode(index - 1);
  56.             removeNode = prevNode.next;
  57.             prevNode.next = null;
  58.             last = prevNode;
  59.         } else { // 删除中间节点
  60.             Node prevNode = getNode(index - 1);
  61.             Node nextNode = prevNode.next.next;
  62.             removeNode = prevNode.next;
  63.             prevNode.next = nextNode;
  64.         }
  65.         size--;
  66.         return removeNode;
  67.     }
  70.     // 得到前置节点
  71.     public static Node getNode(int index) {
  72.         if (index < 0 || index > size) {
  73.             throw new IndexOutOfBoundsException("数组越界");
  74.         }
  75.         Node temp = head;
  76.         for (int i = 0; i < index; i++) {
  77.             temp = temp.next;
  78.         }
  79.         return temp;
  80.     }
  81. }