1. 单链表

  1. /**
  2.  * @Author dyliang
  3.  * @Date 2020/10/2 15:04
  4.  * @Version 1.0
  5.  */
  7. class ListNode{
  8.     int value;
  9.     ListNode next;
  11.     public ListNode(int value) {
  12.         this.value = value;
  13.     }
  14. }
  16. public class SingleDirectionList {
  18.     public static ListNode head = new ListNode(1);
  20.     public static void main(String[] args) {
  21.         ListNode cur = head;
  22.         for (int i = 2; i < 5; i++) {
  23.             cur.next = new ListNode(i);
  24.             cur = cur.next;
  25.         }
  27.         printList(head);
  28.         printList(insertToHead(head, 5));
  29.         printList(insertToList(head, 2, 8));
  30.         printList(removeNode(head, 2));
  31.     }
  34.     // 头部插入
  35.     public static ListNode insertToHead(ListNode head, int value){
  36.         ListNode node = new ListNode(value);
  37.         node.next = head;
  38.         head = node;
  40.         return head;
  41.     }
  43.     // 指定索引处插入指定值的节点
  44.     public static ListNode insertToList(ListNode head, int index, int value){
  45.         if(index < 0 || index > lengthOfList(head)){
  46.             return null;
  47.         }
  49.         ListNode cur = head;
  50.         int l = 0;
  51.         while (cur != null){
  52.             if(l == index - 1){
  53.                 ListNode node = new ListNode(value);
  54.                 node.next = cur.next;
  55.                 cur.next = node;
  56.                 break;
  57.             }else{
  58.                 cur = cur.next;
  59.                 l++;
  60.             }
  61.         }
  63.         return head;
  64.     }
  66.     // 移除指定索引处节点
  67.     public static ListNode removeNode(ListNode head, int index){
  68.         ListNode cur = head;
  69.         int l = 0;
  70.         while (cur != null){
  71.             if(l == index - 1){
  72.                 cur.next = cur.next.next;
  73.                 break;
  74.             }else{
  75.                 cur = cur.next;
  76.                 l++;
  77.             }
  78.         }
  80.         return head;
  81.     }
  83.     // 打印链表
  84.     public static void printList(ListNode head){
  85.         while(head != null){
  86.             System.out.print(head.value + "->");
  87.             head = head.next;
  88.         }
  89.         System.out.println();
  90.     }
  92.     // 链表长度
  93.     public static int lengthOfList(ListNode head){
  94.         int length = 0;
  95.         while(head != null){
  96.             length++;
  97.             head = head.next;
  98.         }
  100.         return length;
  101.     }
  102. }

2. 双向链表

  1. /**
  2.  * @Author dyliang
  3.  * @Date 2020/10/2 15:21
  4.  * @Version 1.0
  5.  */
  7. public class DoubleLinkedList<T> {
  9.     private int size;//链表大小
  10.     private Node<T> head;//链表的头节点
  11.     private Node<T> tail;//链表的尾节点
  13.     /**
  14.      * 内部类：节点
  15.      * @param <T>
  16.      */
  17.     public static class Node<T>{
  18.         private Node prev;
  19.         private Node next;
  20.         private T data;
  22.         public Node(T data){
  23.             this.data = data;
  24.         }
  26.         private Node(){}
  27.     }
  29.     /**
  30.      * 添加到链尾
  31.      * @param data
  32.      */
  33.     public void add(T data){
  34.         add(size, data);
  35.     }
  37.     /**
  38.      * 添加到任意index处
  39.      * @param index
  40.      * @param data
  41.      */
  42.     public void add(int index, T data){
  43.         Node<T> node = new Node<>(data);
  44.         if(isEmpty()) {//链表为空
  45.             head = node;
  46.             tail = node;
  47.         }
  49.         if(index > size - 1){//索引超出当前链表大小，则添加到链尾
  50.             Node<T> temp = tail;
  51.             tail = node;
  52.             temp.next = tail;
  53.             tail.prev = temp;
  54.         }else {//原index位置处有值，索引位置大于index的元素向链尾移动(实际并不是移动，只是看上去)
  55.             Node<T> origin = getNode(index);
  56.             Node<T> prev = origin.prev;
  57.             prev.next = node;
  58.             node.prev = prev;
  59.             node.next = origin;
  60.             origin.prev = node;
  61.         }
  62.         size++;
  63.     }
  65.     /**
  66.      * 更新index位置处元素的值
  67.      * @param index
  68.      * @param data
  69.      */
  70.     public void set(int index, T data){
  71.         if(index > size - 1 || index < 0){
  72.             throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  73.         }
  74.         getNode(index).data = data;
  75.     }
  77.     /**
  78.      * 删除index位置处的元素
  79.      * @param index
  80.      */
  81.     public void delete(int index){
  82.         if(index > size - 1 || index < 0){
  83.             throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  84.         }
  85.         if(index == 0){//删除链头
  86.             head = head.next;
  87.             head.prev = null;
  88.         }else if(index == size -1){//删除链尾
  89.             tail = tail.prev;
  90.             tail.next = null;
  91.         }else {//普通节点
  92.             Node<T> node = getNode(index);
  93.             Node prev = node.prev;
  94.             Node next = node.next;
  95.             prev.next = next;
  96.             next.prev = prev;
  97.             node.prev = null;
  98.             node.next = null;
  99.         }
  100.         size--;
  101.     }
  103.     /**
  104.      * 获取index位置处的元素的值
  105.      * @param index
  106.      * @return
  107.      */
  108.     public T getValue(int index){
  109.         return getNode(index) == null ? null : getNode(index).data;
  110.     }
  112.     public T getValue(Node<T> node){
  113.         return node == null ? null : node.data;
  114.     }
  116.     /**
  117.      * 获取节点node的上一个节点
  118.      * @param node
  119.      * @return
  120.      */
  121.     public Node<T> getPrevNode(Node<T> node){
  122.         return node == null ? null : node.prev;
  123.     }
  125.     /**
  126.      * 获取节点node的下一个节点
  127.      * @param node
  128.      * @return
  129.      */
  130.     public Node<T> getNextNode(Node<T> node){
  131.         return node == null ? null : node.next;
  132.     }
  134.     public Node<T> getHeadNode(){
  135.         return head;
  136.     }
  138.     public Node<T> getTailNode(){
  139.         return tail;
  140.     }
  142.     /**
  143.      * 获取index位置处的元素
  144.      * @param index
  145.      * @return
  146.      */
  147.     public Node<T> getNode(int index){
  149.         if (isEmpty() && (index > size - 1)) {
  150.             throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  151.         }
  152.         Node<T> result = head;
  153.         int n = 0;
  154.         while (n < index) {//注意这里是 n < index， 而不是n <= index
  155.             result = result.next;
  156.             n++;
  157.         }
  158.         return result;
  159.     }
  161.     /**
  162.      * 获取值为data的元素在链表中的位置（第一次出现的位置，可能含有多个）
  163.      * @param data
  164.      * @return
  165.      */
  166.     public int indexOf(T data){
  167.         if(isEmpty() || data == null){
  168.             return -1;
  169.         }
  171.         int n = 0;
  172.         Node<T> node = head;
  173.         while (n < size){
  174.             if(data.equals(node.data)){
  175.                 return n;
  176.             }
  177.             n++;
  178.         }
  180.         return -1;
  181.     }
  183.     /**
  184.      * 判断是否有值为data的元素
  185.      * @param data
  186.      * @return
  187.      */
  188.     public boolean containValue(T data){
  189.         return indexOf(data) != -1;
  190.     }
  192.     /**
  193.      * 获取链表的大小
  194.      * @return
  195.      */
  196.     public int size(){
  197.         return size;
  198.     }
  200.     /**
  201.      * 判断链表是否为空
  202.      * @return
  203.      */
  204.     public boolean isEmpty(){
  205.         return size == 0;
  206.     }
  209. }