✊不积跬步，无以至千里；不积小流，无以成江海。

一、双向链表

  1. public class DuLinkedList<T> implements Iterable<T> {
  3.     // 记录头结点
  4.     private Node head;
  5.     // 记录最后一个结点
  6.     private Node last;
  7.     // 记录链表长度
  8.     private int N;
  10.     public DuLinkedList() {
  11.         // 初始化头结点和尾结点
  12.         last = null;
  13.         head = new Node(null,null,null);
  14.         // 初始化链表长度
  15.         N = 0;
  16.     }
  18.     // 清空链表
  19.     public void clear() {
  20.         this.head.next = null;
  21.         this.last = null;
  22.         this.N = 0;
  23.     }
  25.     // 获取链表的长度
  26.     public int length() {
  27.         return N;
  28.     }
  30.     // 判断链表是否为空
  31.     public boolean isEmpty() {
  32.         return N == 0;
  33.     }
  35.     // 获取第一个元素
  36.     public T getFirst() {
  37.          if (isEmpty()) {
  38.              return null;
  39.          }
  40.          return head.next.item;
  41.     }
  43.     // 获取最后一个元素
  44.     public T getLast() {
  45.         if (isEmpty()) {
  46.             return null;
  47.         }
  48.         return last.item;
  49.     }
  51.     // 插入元素t
  52.     public void insert(T t) {
  53.         if (isEmpty()) {
  54.             // 创建新结点
  55.             Node newNode = new Node(t, head, null);
  56.             // 新结点成为尾结点
  57.             last = newNode;
  58.             // 头结点指向尾结点
  59.             head.next = last;
  61.         } else {
  62.             Node oldLast = last;
  63.             Node newNode = new Node(t, oldLast, null);
  64.             oldLast.next = newNode;
  65.             last = newNode;
  66.         }
  67.         // 元素个数加1
  68.         N++;
  69.     }
  71.     // 向指定位置i处插入元素t
  72.     public void insert(T t, int i) {
  73.         // 先找到第i个元素的前一个结点
  74.         Node pre = head;
  75.         for (int index=0; index<i; index++) {
  76.             pre = pre.next;
  77.         }
  78.         // 找到第i个结点
  79.         Node curr = pre.next;
  80.         // 创建新结点
  81.         Node newNode = new Node(t, pre, curr);
  82.         // 第i个结点的上一个结点的下一个结点为新结点
  83.         pre.next = newNode;
  84.         // 第i个结点的上一个结点为新结点
  85.         curr.pre = newNode;
  86.         // 链表长度加1
  87.         N++;
  88.     }
  90.     // 获取指定位置i处的元素
  91.     public T get(int i) {
  92.         Node curr = head;
  93.         for (int index=0; index<i; index++) {
  94.             curr = curr.next;
  95.         }
  96.         return curr.next.item;
  97.     }
  99.     // 找到元素t在链表中第一次出现的位置
  100.     public int indexOf(T t) {
  101.         Node curr = head;
  102.         for (int i=0; curr.next != null; i++) {
  103.             curr = curr.next;
  104.             if (t.equals(curr.item)) {
  105.                 return i;
  106.             }
  107.         }
  108.         return -1;
  109.     }
  111.     // 删除指定i位置元素，并返回该元素
  112.     public T remove(int i) {
  113.         // 先找到第i个结点的上一个结点
  114.         Node pre = head;
  115.         for (int index=0; index<i; index++) {
  116.             pre = pre.next;
  117.         }
  118.         // 找到第i个结点
  119.         Node curr = pre.next;
  120.         // 第i个结点的上一个结点指向第i个结点的下一个结点
  121.         pre.next = curr.next;
  122.         // 第i个结点的下一个结点指向第i个结点的上一个结点
  123.         curr.pre = pre;
  124.         // 链表长度减1
  125.         N--;
  126.         return curr.item;
  127.     }
  129.     private class Node {
  131.         public Node(T item, Node pre, Node next) {
  132.             this.item = item;
  133.             this.pre = pre;
  134.             this.next = next;
  135.         }
  137.         // 存储数据
  138.         public T item;
  139.         // 上一个结点
  140.         public Node pre;
  141.         // 下一个结点
  142.         public Node next;
  144.     }
  146.     /**
  147.      * 遍历链表
  148.      * @return
  149.      */
  150.     @Override
  151.     public Iterator iterator() {
  152.         return new MyIterator();
  153.     }
  155.     private class MyIterator implements Iterator {
  157.         private Node n;
  158.         public MyIterator(){
  159.             this.n = head;
  160.         }
  162.         @Override
  163.         public boolean hasNext() {
  164.             return n.next != null;
  165.         }
  167.         @Override
  168.         public Object next() {
  169.             n = n.next;
  170.             return n.item;
  171.         }
  172.     }
  174.     // 反转链表
  175.     public void reverse() {
  176.         if (isEmpty()){
  177.             return;
  178.         }
  179.         reverse(head.next);
  180.     }
  182.     // 递归反转链表,并返回当前节点
  183.     public Node reverse(Node curr) {
  184.         if (curr.next == null) {
  185.             // 头结点指向最后一个结点
  186.             head.next = curr;
  187.             return curr;
  188.         }
  189.         // 递归反转当前节点的下一个结点，返回反转后下一个结点的前一个结点为当前节点
  190.         Node pre = reverse(curr.next);
  191.         pre.next = curr;
  192.         // 将当前结点的下一个结点为null
  193.         curr.next = null;
  194.         return curr;
  195.     }
  197. }

二、队列

  1. package com.linjie.test.linear;
  3. import java.util.Iterator;
  5. /**
  6.  * @Title：Queue
  7.  * @Package：com.linjie.test.linear
  8.  * @Description：
  9.  * @author：done
  10.  * @date：2021/11/24 19:47
  11.  */
  12. public class Queue<T> implements Iterable<T>{
  14.     // 记录首结点
  15.     private Node head;
  16.     // 记录最后一个结点
  17.     private Node last;
  18.     // 当前栈的元素个数
  19.     private int N;
  21.     private class Node{
  22.         public T item;
  23.         public Node next;
  25.         public Node(T item, Node next){
  26.             this.item = item;
  27.             this.next = next;
  28.         }
  29.     }
  31.     // 队列
  32.     public Queue(){
  33.         this.head = new Node(null, null);
  34.         this.N = 0;
  35.         this.last = null;
  36.     }
  38.     // 判断队列是否为空
  39.     public boolean isEmpty(){
  40.         return N == 0;
  41.     }
  43.     // 返回队列的元素个数
  44.     public int size(){
  45.         return N;
  46.     }
  48.     // 向队列中插入元素t
  49.     public void enqueue(T t){
  50.         if (last == null){
  51.             last = new Node(t, null);
  52.             head.next = last;
  53.         } else {
  54.             Node oldNode = last;
  55.             last = new Node(t, null);
  56.             oldNode.next = last;
  57.         }
  58.         // 元素个数加1
  59.         N++;
  60.     }
  62.     // 从队列中拿出一个元素
  63.     public T dequeue(){
  64.         if (isEmpty()){
  65.             return null;
  66.         }
  67.         Node oldFirst = head.next;
  68.         head.next = oldFirst.next;
  69.         N--;
  71.         // 出队列实际为删除元素，若队列为空，需重置
  72.         if (isEmpty()){
  73.             last = null;
  74.         }
  75.         return oldFirst.item;
  76.     }
  78.     @Override
  79.     public Iterator<T> iterator() {
  80.         return new MyIterator();
  81.     }
  83.     private class MyIterator implements Iterator{
  85.         private Node n;
  87.         public MyIterator(){
  88.             this.n = head;
  89.         }
  91.         @Override
  92.         public boolean hasNext() {
  93.             return n.next != null;
  94.         }
  96.         @Override
  97.         public Object next() {
  98.             n = n.next;
  99.             return n.item;
  100.         }
  101.     }
  103. }