数据结构-链表（一）单向

定义：

数据元素的线性集合，每个元素都指向下一个元素，元素存储不连续

---

简单分类：

• 单向链表：每个元素只指向下一个元素

• 双向链表：每个元素指向上一个和下一个元素

• 循环链表：通常链表尾节点 tail 指向为 null ，而循环链表指向为头结点 head

  ---

性能：

随机访问：

• 根据index查找，时间复杂度O(n)

插入或删除：

• 起始位置：O(1)

• 结束位置：如果已知尾节点，则O(1)，反之O(n)

• 中间位置：根据index查找时间 + O(1)

---

代码实现——Java

• 定义节点类

  public class SinglyLinkedList implements Iterable<Integer> {
      private Node_ head = null;
  
      //节点类
      private static class Node_ {
          int value;//节点值
          Node_ next;//指向下一个节点
  
          public Node_(int value, Node_ next) {
              this.value = value;
              this.next = next;
          }
      }

• 头插法添加索引

  //头插法
  public void addToFirst(int value) {
      head = new Node_(value, head);
  }

• 根据给定索引返回节点

  //根据给定索引返回节点
  private Node_ findByIndex(int index) {
      int i = 0;
      for (Node_ cur = head; head != null; cur = cur.next, i++) {
          if (i == index) return cur;
      }
      return null;
  }

• 尾插法

  //尾插法
  public void addToLast(int value) {
      Node_ last = findLast();
      if (last == null) {
          head = new Node_(value, null);
      } else {
          last.next = new Node_(value, null);
      }
  }

• 根据索引插入

  //根据合法索引插入节点
  public void insert(int index, int value) {
      if (index == 0) {
          addToFirst(value);
          return;
      }
      //当前节点的上一个节点
      Node_ cur = findByIndex(index - 1);
      if (cur == null) throw getIllegalArgumentException(index);
      cur.next = new Node_(value, cur.next);
  }

• 删除节点

  //删除头结点
  public void deleteToFirst(){
      if (head == null){
          throw getIllegalArgumentException(0);
      }
      head = head.next;
  }
  //根据索引删除节点
  public void deleteByIndex(int index){
      if (index == 0){
          deleteToFirst();
          return;
      }
      Node_ cur = findByIndex(index - 1);
      if (cur == null){
          throw getIllegalArgumentException(index);
      }
      cur.next = cur.next.next;
  }

• 遍历节点

  //遍历节点
  public void loop(Consumer<Integer> consumer) {
      Node_ cur = head;
      while (cur != null) {
          consumer.accept(cur.value);
          cur = cur.next;
      }
  }
  public void loop2(Consumer<Integer> consumer) {
      for (Node_ cur = head; cur != null; cur = cur.next) {
          consumer.accept(cur.value);
      }
  }
  //迭代器
  @Override
  public Iterator<Integer> iterator() {
      return new Iterator<>() {
          Node_ cur = head;
      
          @Override
          public boolean hasNext() {//是否有下一个元素
              return cur != null;
          }
      
          @Override
          public Integer next() {//返回当前元素的值，并指向下一个元素
              int value = cur.value;
              cur = cur.next;
              return value;
          }
      };
  }

使用哨兵节点

• 哨兵节点：也称为哑元节点，不存储数据，通常当做首尾，简化边界判断

我们对一些代码进行改动，因为索引的开头不再是Node，而是一个哨兵；

• 头插法

  public void addToFirst(int value) {
      insert(0,value)
  }

• 尾插法

  public void addToLast(int value) {
      Node_ last = findLast();
      last.next = new Node_(value, null);
  }

• 按索引插入

  public void insert(int index, int value) {
      Node_ cur = findByIndex(index - 1);
      if (cur == null) throw getIllegalArgumentException(index);
      cur.next = new Node_(value, cur.next);
  }

• 按索引返回节点

  private Node_ findByIndex(int index) {
      int i = -1;
      for (Node_ cur = head; cur != null; cur = cur.next, i++) {
          if (i == index) return cur;
      }
      return null;
  }

---

什么时候要用static呢？

• 当某一个内部类使用了外部类的属性的时候不能使用 static ，静态类只能引用静态的变量和方法

• 当一个内部类相对独立时可以使用 static

• 建议能加尽量加 （）