目录

01 简介

02 接口设计

03 clear

04 add

05 remove

06 indexOf_toString

07 删除节点

08 反转链表( 递归)

09 反转链表(迭代)

10 反转链表(环形链表)

11 补充

12 虚拟头节点

13 复杂度分析(ArrayList)

14 均摊度分析

15 ArrayList的缩容

16 复杂度震荡

01 简介

• 简介是如下所示:
• 链表的设计方案是如下所示:
•  链表的设计代码是如下所示:

  public class LinkedList {
      private int size;
      private Node firstNode;//由于是只是在链表之中进行使用,因此我们设计成内部类
  
  
      private static class Node//这里的节点内部类要进行设计成为相应的私有静态的,不要问为什么.
      {
          E element;//内部类是一般不写访问的权限的
          Node next;
  
          //构造函数
          public Node(E element, Node next) {
              this.element = element;
              this.next = next;
          }
      }
  }

02 接口设计

• 链表的接口大部分和动态数组是一致的.因此,创建一个父类List,只是数组和链表的实现方式是不一样的.

          但是这里二者数组和链表内容是完全不一样的,使用父类的方式并不是最佳的方式进行,可以使用接口进行创建.

 

•  ArrayList和LinkedList还是存在一定的公共的相同的东西,因此,这里还是可以使用公共的线型表进行表示.
•  经过上述处理之后List接口的代码是:

  public interface List {
  
     static final int ELEMENT_NOT_FOUND = -1;
  
  
      void clear();
  
      int size();
  
      boolean isEmpty();
  
      boolean contains(E var1);
  
      void add(E var1);
  
      E get(int var1);
  
      E set(int var1, E var2);
  
      void add(int var1, E var2);
  
      E remove(int var1);
  
      int indexOf(E var1);
  
  }
  

  AbstractList之中的代码是:

  public abstract class AbstractList implements List{//这里是只是实现一些公共的方法,因此,这里是使用abstract方式,对于外界是不可见的.
  
  
  
      protected int size;
  
      public int size() {
          return size;
      }
  
      
      public boolean isEmpty() {
          return size == 0;
      }
  
      
      public boolean contains(E element) {
          return indexOf(element) != ELEMENT_NOT_FOUND;
      }
  
      
      public void add(E element) {
          if(element == null) return;
  
          add(size, element);
      }
  
      protected void outOfBounds(int index) {
          throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
      }
  
      protected void rangeCheck(int index) {
          if (index < 0 || index >= size) {
              outOfBounds(index);
          }
      }
  
      protected void rangeCheckForAdd(int index) {
          if (index < 0 || index > size) {
              outOfBounds(index);
          }
      }
  }
  

  ArrayList之中的代码是:

  
  public class ArrayList extends AbstractList {
      
  
      
      private E[] elements;
  
      private static final int DEFAULT_CAPACITY = 10;
  
  
      public ArrayList(int capaticy) {
          capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
          elements = (E[]) new Object[capaticy];
      }
  
      public ArrayList() {
          this(DEFAULT_CAPACITY);
      }
  
      
      public void clear() {
          
          for (int i = 0; i < size; i++) {
              elements[i] = null;
          }
          size = 0;
      }
  
  
      
      public E get(int index) {
          rangeCheck(index);
          return elements[index];
      }
  
      
      public E set(int index, E element) {
          rangeCheck(index);
  
          E old = elements[index];
          elements[index] = element;
          return old;
      }
  
      
      public void add(int index, E element) {
          rangeCheckForAdd(index);
  
          ensureCapacity(size + 1);
  
          for (int i = size; i > index; i--) {
              elements[i] = elements[i - 1];
          }
          elements[index] = element;
          size++;
      }
  
      
      public E remove(int index) {
          rangeCheck(index);
  
          E old = elements[index];
          for (int i = index + 1; i < size; i++) {
              elements[i - 1] = elements[i];
          }
          elements[--size] = null;
          return old;
      }
      public  void  remove(E element)
      {
          remove(indexOf(element));
      }
  
      
      public int indexOf(E element) {
          if (element == null) {  // 1
              for (int i = 0; i < size; i++) {
                  if (elements[i] == null) return i;
              }
          } else {
              for (int i = 0; i < size; i++) {
                  if (element.equals(elements[i])) return i; // n
              }
          }
          return ELEMENT_NOT_FOUND;
      }
  
  //	public int indexOf2(E element) {
  //		for (int i = 0; i < size; i++) {
  //			if (valEquals(element, elements[i])) return i; // 2n
  //		}
  //		return ELEMENT_NOT_FOUND;
  //	}
  //
  //	private boolean valEquals(Object v1, Object v2) {
  //		return v1 == null ? v2 == null : v1.equals(v2);
  //	}
  
      
      private void ensureCapacity(int capacity) {
          int oldCapacity = elements.length;
          if (oldCapacity >= capacity) return;
  
          // 新容量为旧容量的1.5倍
          int newCapacity = oldCapacity + (oldCapacity >> 1);
          E[] newElements = (E[]) new Object[newCapacity];
          for (int i = 0; i < size; i++) {
              newElements[i] = elements[i];
          }
          elements = newElements;
  
          System.out.println(oldCapacity + "扩容为" + newCapacity);
      }
  
  
      @Override
      public String toString() {
          // size=3, [99, 88, 77]
          StringBuilder string = new StringBuilder();
          string.append("size=").append(size).append(", [");
          for (int i = 0; i < size; i++) {
              if (i != 0) {
                  string.append(", ");
              }
  
              string.append(elements[i]);
  
  //			if (i != size - 1) {
  //				string.append(", ");
  //			}
          }
          string.append("]");
          return string.toString();
      }
  }
  

  LinkedList之中的代码是:

  public class LinkedList extends AbstractList{
      int ELEMENT_NOT_FOUND = -1;
      private int size;
      private Node firstNode;//由于是只是在链表之中进行使用,因此我们设计成内部类
  
      private static class Node//这里的节点内部类要进行设计成为相应的私有静态的,不要问为什么.
      {
  
  
          E element;//内部类是一般不写访问的权限的
          Node next;
  
          //构造函数
          public Node(E element, Node next) {
              this.element = element;
              this.next = next;
          }
      }
  
      public void clear() {
  
  
  
      }
  
      public int size() {
          return size;
      }
  
      public boolean isEmpty() {
          return size == 0;
      }
  
      public boolean contains(E element) {
          return indexOf(element) !=  ELEMENT_NOT_FOUND ;
      }
  
      public void add(E element) {
          add(size,element);
  
      }
  
      public E get(int var1) {
          return null;
      }
  
      public E set(int var1, E var2) {
          return null;
      }
  
      public void add(int var1, E var2) {
  
      }
  
      public E remove(int var1) {
          return null;
      }
  
      public int indexOf(E var1) {
          return 0;
      }
  
  
  
  
  }
  

03 clear

• 清空元素
•  代码块如下所示:

    public void clear() {
        size = 0;
        first = null;
    }

04 add

• 添加元素的结构示意图:
•  通过index获取相应的节点的方式是如下所示:

   
    private Node node(int index)//这里的含义就是传入一个索引,返回当下的节点
    {
        //检查索引是否存在
        rangeCheck(index);

        //比如,想要找到索引为2的位置,需要索引进行next两次
        Node node = first;
        for (int i = 0;i < index;i++)
        {
            node = node.next;
        }
        return node;
    }

• 由上所示,可以得知set和get方法的使用:

 

    public E get(int index) {
        return node(index).element;
    }

    public E set(int index, E element) {
        Node node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }

• 添加元素的代码是如下所示:

      public void add(int index, E element) {
          //如果要是传入的index是0
          if(index == 0)//添加到最前面的位置
          {
          first = new Node<>(element,first);
          }
          else
          {    Node prev = node(index-1);
              prev.next = new Node(element,prev.next); //这是
  
          }
  
          size++;
  
      }

   注意:临界和边界位置处理

05 remove

• 删除元素

    public E remove(int index) {
        
        //被删除的节点
        Node node = first;
        
       if(index == 0)
       {
           first = first.next;
       }
       else
       {
           Node prev = node(index-1);
           node = prev.next;
           prev.next = prev.next.next;
       }
size--;
       return node.element;
    }

06 indexOf_toString

    private Node node(int index)//这里的含义就是传入一个索引,返回当下的节点
    {
        //检查索引是否存在
        rangeCheck(index);

        //比如,想要找到索引为2的位置,需要索引进行next两次
        Node node = first;
        for (int i = 0;i < index;i++)
        {
            node = node.next;
        }
        return node;
    }

    @Override
    public String toString() {
        
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(", [");
        Node node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }

            string.append(node.element);

            node = node.next;
        }
        string.append("]");
        return string.toString();
    }

07 删除节点

• 一个神奇的网站https://visualgo.net/zh
• 刷个题: ​​​​​​237. 删除链表中的节点 - 力扣（LeetCode）https://leetcode.cn/problems/delete-node-in-a-linked-list/这里的方式是进行覆盖的过程,使用下一个的值去指向前一个节点的值,指针的改变和以往是一样的.

08 反转链表( 递归) 刷题:

• 206. 反转链表 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-linked-list/

• 代码段如下所示:

  package 链表;
  
  public class _206_反转链表 {
      
      class Solution {
          public class ListNode {
              int val;
              ListNode next;
  
              ListNode() {
              }
  
              ListNode(int val) {
                  this.val = val;
              }
  
              ListNode(int val, ListNode next) {
                  this.val = val;
                  this.next = next;
              }
          }
  
          public ListNode reverseList(ListNode head) {
              if(head == null)
                  return null;
  
              if(head.next == null) return head;
  
              ListNode newHead = reverseList(head.next);
  
              head.next.next = head;//4的next指向5
  
              head.next = null;//5的next指向null
  
              return newHead;
  
  
          }
      }
  }

09 反转链表(迭代)

• 代码思路:重复上述操作,将上面的东西进行串联.
•  代码块是如下所示:

    public ListNode reverseList2(ListNode head) {
              if(head == null)
                  return null;
  
              if(head.next == null) return head;
  
             ListNode newHead = null;
             while(head != null) {
                 ListNode tmp = head.next;
                 head.next = newHead;
                 newHead = head;
                 head = tmp;
  
             }
              return newHead;
  
          }

10 反转链表(环形链表)

• 刷题141. 环形链表 - 力扣（LeetCode）https://leetcode.cn/problems/linked-list-cycle/
• 使用快慢指针思想进行解决.这里快慢指针的含义就是,比如说慢指针走一个,快指针走两个,如果要是又环的话,二者就是一定会相遇的.
• 判断是否有环的过程之中,代码实现.

  package 链表;
  
  public class _3_判断一个链表是否有环 {//141题
  
          public boolean hasCycle(ListNode head) {
              if (head == null && head.next == null) return false;
  
              ListNode slow = head;
              ListNode fast = head.next;
              while (fast != null && fast.next != null) //这里是防止空指针异常的情况出现
              {
                  slow = slow.next;
                  fast = fast.next.next;
  
                  if(fast == slow) return true;
                  
              }
              return false;
          }
  
  }

11 补充

• 这里需要进行注意的是remove方法之中存在首指针为0的情况,add方法之中也是需要进行注意:

12 虚拟头节点

• 使得代码更加的精简
•  虚拟头节点的存在使得相应的add和remove以及toString方式存在差异.
• ArrayList2代码:

  //
  // Source code recreated from a .class file by IntelliJ IDEA
  // (powered by Fernflower decompiler)
  //
  
  package com.mj;
  
  public class ArrayList2 extends AbstractList {
      private E[] elements;
      private static final int DEFAULT_CAPACITY = 10;
  
      public ArrayList2(int capaticy) {
          capaticy = capaticy < 10 ? 10 : capaticy;
          this.elements = new Object[capaticy];
      }
  
      public ArrayList2() {
          this(10);
      }
  
      public void clear() {
          for(int i = 0; i < this.size; ++i) {
              this.elements[i] = null;
          }
  
          this.size = 0;
          if (this.elements != null && this.elements.length > 10) {
              this.elements = new Object[10];
          }
  
      }
  
      public E get(int index) {
          this.rangeCheck(index);
          return this.elements[index];
      }
  
      public E set(int index, E element) {
          this.rangeCheck(index);
          E old = this.elements[index];
          this.elements[index] = element;
          return old;
      }
  
      public void add(int index, E element) {
          this.rangeCheckForAdd(index);
          this.ensureCapacity(this.size + 1);
  
          for(int i = this.size; i > index; --i) {
              this.elements[i] = this.elements[i - 1];
          }
  
          this.elements[index] = element;
          ++this.size;
      }
  
      public E remove(int index) {
          this.rangeCheck(index);
          E old = this.elements[index];
  
          for(int i = index + 1; i < this.size; ++i) {
              this.elements[i - 1] = this.elements[i];
          }
  
          this.elements[--this.size] = null;
          this.trim();
          return old;
      }
  
      public int indexOf(E element) {
          int i;
          if (element == null) {
              for(i = 0; i < this.size; ++i) {
                  if (this.elements[i] == null) {
                      return i;
                  }
              }
          } else {
              for(i = 0; i < this.size; ++i) {
                  if (element.equals(this.elements[i])) {
                      return i;
                  }
              }
          }
  
          return -1;
      }
  
      private void ensureCapacity(int capacity) {
          int oldCapacity = this.elements.length;
          if (oldCapacity < capacity) {
              int newCapacity = oldCapacity + (oldCapacity >> 1);
              Object[] newElements = new Object[newCapacity];
  
              for(int i = 0; i < this.size; ++i) {
                  newElements[i] = this.elements[i];
              }
  
              this.elements = newElements;
              System.out.println(oldCapacity + "扩容为" + newCapacity);
          }
      }
  
      private void trim() {
          int oldCapacity = this.elements.length;
          int newCapacity = oldCapacity >> 1;
          if (this.size <= newCapacity && oldCapacity > 10) {
              Object[] newElements = new Object[newCapacity];
  
              for(int i = 0; i < this.size; ++i) {
                  newElements[i] = this.elements[i];
              }
  
              this.elements = newElements;
              System.out.println(oldCapacity + "缩容为" + newCapacity);
          }
      }
  
      public String toString() {
          StringBuilder string = new StringBuilder();
          string.append("size=").append(this.size).append(", [");
  
          for(int i = 0; i < this.size; ++i) {
              if (i != 0) {
                  string.append(", ");
              }
  
              string.append(this.elements[i]);
          }
  
          string.append("]");
          return string.toString();
      }
  }
  

  一般不建议是使用添加虚拟头节点的方式进行.

13 复杂度分析(ArrayList)

• 复杂度的三种情况:

• 数组访问一个元素,速度是一致的,随机访问是非常快的. 数据规模是指元素的数量,O(n).
• 只有和数据规模相关的时候,才会分析相应的三种复杂度的情况.拿add方式进行分析,如下所示(remove方式是与add方式相同的):最好的情况是:O(1),最坏情况是O(n),平均是O(n).
• 链表的添加 删除的复杂度是O(1),是指添加 删除那一刻.
• 动态数组 链表复杂度分析

14 均摊度分析

15 ArrayList的缩容

16 复杂度震荡