• 昨天在学习顺序结构的内容时感觉并不难,但是你会在编写代码的时候发现他的结构的弊端

  • 只要是扩容,或者中间插入,那么你必须把数组拷贝来拷贝去的麻烦
  • 昨天在测试一千万还是五千万的时候,由于需要分配内存空间,直接涨上1G的使用空间,如果你电脑没有这个内存富余,那么分配空间很可能会会失败掉
• 为了克服上面的问题,那么我们今天来学习饿线性表的链式结构

什么是链表

• 典型的链表结构中的节点包含两部分

  • 你需要存储的数据
  • 既然叫链式,那么肯定是有下一个数据节点的引用,结构如图

• 如上我们就能很清晰的看到他的结构到底是怎么样的,在链表中,需要有一个"头引用"地址来指向第一个元素,而第一个在指向下一个元素,以此类推,直到某个元素的地址引用为null,表示链表到头了,因为他找不到下一个元素在那里了,所以这个节点就是尾节点,地址为null以表示链表结束
• 与顺序结构的区别
• 打开昨天的文章,我们发现的第一点区别就是链表比顺序多了指向,顺序表的逻辑结构和物理结构是一样的,都是连续地址存放,而链表则不同,他在物理存储的时候并不一定是连续存储的,逻辑上的引用关系通过地址部分的引用变量来实现的

• 好了我们知道了两个表的结构上的区别,所以我们就可以分析出了链表的优势在哪里

  • 不像顺序结构需要连续地址,插入或者扩容需要大量移动元素,而链表的处理方式就是直接改变引用就可以了,如下图
  • 链表不需要连续存放,因此在保存大量数据的时候,不需要分配一块连续空间,可以动态的插入,比如你要存点A,直接把点A的地址改变到下一个节点地址,然后改变上一个元素地址即可

• 与顺序表相比缺点也是显而易见的,

  • 那就是耗费空间,因为他多保存了一个地址引用,但是当你在操作大量元素的时候,这个缺点完全可以忽略
  • 还有一个缺点,我们回想昨天的顺序表结构,他取值是直接拿数组下标即可,那么我们分析到这,链表好像没有下表,那么该怎么取得值呢?只能去遍历链表,所以我们总结出链表适合增删,不适合查找修改

链表实现形式

• 单向链表:就是最开始的那种图
• 双向链表:就是单向链表的双地址版,不仅仅保存了下一个节点地址,还保存了上一个节点地址

• 单向循环链表:就是单向链表的尾节点连接到头结点地址上,形成一个回环

• 双向循环链表:就是双向链表的头尾相连,形成回环

头指针和头节点

• 这是两个不同的东西,刚开始自己写代码也是不清楚,所以很头疼,下面这幅图你应该就知道区别了

• 如上图,头指针只是一个指向而已,并不是真正的(数据+地址),仅仅是指向头节点而已,如果有尾指针,那么意思是相同的,也就是只指向最后一个尾节点

单向链表实现

• 单项列表的结构简单,但是在自己的代码实现中,删除操作,需要一个额外的指针

• 如上,因为每个节点中只是保留了你下一个节点的地址,如果你遍历到了这个节点,这个节点就是你要删除的节点,那么你需要做的是把上一个节点和下一个节点链接起来,但是你遍历到此节点后,你上一个节点的信息已经遍历过去了,回不去了,所以我们就需要额外的保存已经遍历过的上一个节点

   
  public class MyLinkedList<T> {
  
      //添加的数据的个数
      private int size;
      //头指针
      private Node<T> head;
      //尾指针
      private Node<T> tail;
  
      public MyLinkedList() {
          //初始化时候,头指针为空
          head = new Node<>(null,null);
          //因为没有元素,所以头指针尾指针是一个
          tail = head;
      }
  
      //添加元素
      public void add(int index ,T element) {
          int i = -1;
          for (Node<T> x = head; x != null; x = x.behind) {
              if (i == index -1){
                  Node<T> next = x.behind;
                  x.behind = new Node<>(next,element);
                  break;
              }
              i ++;
          }
          size ++;
      }
      //增加元素
      public void addLast(T element){
          //如果头指针指向都是空的那么这个肯定是一个空链表
          if (head.behind == null){
              //空链表添加,就是新建节点的过程,新建的节点由于是第一个,那么他的后面是没有节点的
              head.behind = new Node<>(null,element);
              //就一个节点,尾指针就指向这个唯一节点
              tail = head.behind;
          }else {
              //证明链表不为空,由于是在最后添加操作
              //需要将tail暂时保存
              Node<T> node = tail;
              //tail指向新节点
              tail = new Node<>(null,element);
              //原来最后一个节点就是现在的尾指针指向的节点
              node.behind = tail;
          }
          size ++;
      }
      //增加元素
      public void addFirst(T element){
          //之前跟addLast一致
          if (head.behind == null){
              head.behind = new Node<>(null,element);
              tail = head.behind;
          }else {
              //向最开始添加节点,那么就需要保存最开始节点的引用
              Node<T> node = head.behind;
              //然后头指针指向最新插入的节点,该节点的构造方法中指向原来第一个节点
              head.behind = new Node<>(node,element);
          }
          size ++ ;
      }
      //删除元素
      public void remove(T element){
          //空链表直接返回
          if (null == head.behind) return;
          Node<T> per;   //这就是文章中说的,暂时保存前一个节点引用的
          //第一个节点
          Node<T> node = head.behind;
          //头指针
          per = head;
          while (true){
              //如果节点的数据与删除数据一致
              if (node.element.equals(element)){
                  //==
                  //就是该节点的前一个节点指向该节点的下一个节点
                  per.behind = node.behind;
                  //删除完成
                  size --;
                  break;
              }else {
                  //如果不一致,就需要将这个节点暂时保存
                  per = node ;
                  //如果这个节点没有下面的节点了,代表结尾了
                  if (node.behind == null){
                      //tail node.behind == null & !equals = no node
                      //到尾节点了,而且尾节点的数据与传入不一致,代表整个链表没有此数据
                      //退出
                      break;
                  }else {
                      //代表此node还有下一个节点
                      //那么就移动指向,移到下一个节点再while判断
                      node = node.behind;
                  }
              }
          }
      }
  
      //跟上面的方法大同小异,而且比上面的逻辑简单
      public void remove(int index){
          if (null == head.behind) return;
          Node<T> per;
          Node<T> node = head.behind;
          per = head;
          for (int i = 0; i <= index; i++) {
              if (i == index){
                  //==
                  per.behind = node.behind;
                  break;
              }else {
                  per = node ;
                  if (node.behind == null){
                      //tail node.behind == null & !equals = no node
                      break;
                  }else {
                      node = node.behind;
                  }
              }
          }
      }
  
      //修改元素
      public void update(int index,T element){
          //为什么是-1.因为下面的循环是从head头指针开始的,头指针是不算数的
          int i = -1;
          for (Node<T> x = head; x != null; x = x.behind) {
              if (i == index){
                  x.element = element;
                  break;
              }
              i++;
          }
      }
  
      //查找元素
      public int getIndex(T element){
          if (head.behind == null )
              return -1;
          int i = 0 ;
          for (Node<T> x = head.behind; x != null; x = x.behind) {
              if (x.element.equals(element)){
                  return i;
              }
              i++;
          }
          return -1;
      }
      //是否包含某个元素
      public boolean contains(T element){
          if (head.behind == null )
              return false;
          for (Node<T> x = head.behind; x != null; x = x.behind) {
              if (x.element.equals(element)){
                  return true;
              }
          }
          return false;
      }
      //元素个数
  
      public int getSize() {
          return size;
      }
  
      //代表图中的data+addr部分
      private class Node<T>{
          Node<T> behind;//指向后面元素的指针
          T element; //当前数据
          public Node(Node<T> behind, T element) {
              this.behind = behind;
              this.element = element;
          }
      }
      @Override
      public String toString() {
          if (head == null){
              return "{}";
          }
          Node<T> firstNode = head.behind;
          Node<T> node = new Node<>(firstNode.behind,firstNode.element);
          StringBuilder buffer = new StringBuilder();
          while (true){
              if (node == null){
                  break;
              }else {
                  buffer.append(node.element + " , ");
                  node = node.behind;
              }
          }
          return buffer.toString();
      }
  }

• 测试

  public static void main(String[] args) {
          MyLinkedList<String> linkedList = new MyLinkedList<>();
          linkedList.addLast("1");
          linkedList.addLast("2");
          linkedList.addLast("3");
          linkedList.addLast("4");
          linkedList.addLast("5");
          linkedList.addFirst("0");
          linkedList.addFirst("-1");
          System.out.println(linkedList);
  
          linkedList.remove("0");
          System.out.println(linkedList);
          linkedList.remove(0);
          System.out.println(linkedList);
          linkedList.remove(4);
          System.out.println(linkedList);
          linkedList.add(2,"s");
          System.out.println(linkedList);
          linkedList.add(4,"p");
          System.out.println(linkedList);
          linkedList.update(0,"x");
          System.out.println(linkedList);
          linkedList.update(3,"z");
          System.out.println(linkedList);
          int x = linkedList.getIndex("x");
          System.out.println(x);
          int z = linkedList.getIndex("z");
          System.out.println(z);
          boolean x1 = linkedList.contains("x");
          System.out.println(x1);
          System.out.println(linkedList.contains("2"));
          System.out.println(linkedList.contains("yyy"));
      }

• 结果

  -1 , 0 , 1 , 2 , 3 , 4 , 5 ,
  -1 , 1 , 2 , 3 , 4 , 5 ,
  1 , 2 , 3 , 4 , 5 ,
  1 , 2 , 3 , 4 ,
  1 , 2 , s , 3 , 4 ,
  1 , 2 , s , 3 , p , 4 ,
  x , 2 , s , 3 , p , 4 ,
  x , 2 , s , z , p , 4 ,
  0
  3
  true
  true
  false

• 里面的内部类Node,就是每个节点,里面存放了指向和数据

双向循环链表

• 我们也来实现一个双向的链表,其主要的链接操作,所以如图

• 其实实现的重点在于add方法,如果你可以将上面的单链表的理解了,那么下面的就跟闹着玩似的,自我感觉双向的比单向的好写

• 上面是新增元素的一个过程,拆除原来的互相引用,而转链接到新元素到,那么删除的话,就是一个反过程,将要被删除的元素上的所以指向删除,然后该元素的前一个元素引用该元素后面的元素,后面的元素引用前面的元素,如果该元素为a,那么就是a+1互相引用a-1,知道了最麻烦的步骤,下面就是实现代码

  public class DoubleLink<T> {
      private int size;
      private Node<T> head;
      private Node<T> tail;
  
      public DoubleLink() {
          head = new Node<>();
          tail = new Node<>();
          head.front = tail;
          head.next = tail;
          tail.front = head;
          tail.next = head;
      }
  
      private class Node<T> {
          private Node<T> front;
          private T element;
          private Node<T> next;
  
          public Node() {
          }
  
          public Node(Node<T> front, T element, Node<T> next) {
              this.front = front;
              this.element = element;
              this.next = next;
          }
  
          @Override
          public String toString() {
              return "" + element;
          }
      }
  
      //增
      public void addLast(T element) {
          if (0 == size) {
              Node<T> node = new Node<>(head, element, tail);
              head.next = node;
              tail.front = node;
          } else {
              Node<T> tailNodeFront = tail.front;
              Node<T> node = new Node<>(tailNodeFront, element, tail);
              tailNodeFront.next = node;
              tail.front = node;
          }
          size++;
      }
  
      public void addFirst(T element) {
          if (0 == size) {
              Node<T> node = new Node<>(head, element, tail);
              head.next = node;
              tail.front = node;
          } else {
              Node<T> headNextNode = head.next;
              Node<T> node = new Node<T>(head, element, headNextNode);
              head.next = node;
              headNextNode.front = node;
          }
          size++;
      }
  
      public void add(int index, T element) {
          if (0 == size) {
              Node<T> node = new Node<>(head, element, tail);
              head.next = node;
              tail.front = node;
          } else {
              int i = -1;
              for (Node<T> node = head; node != null; node = node.next) {
                  if (i == index) {
                      Node<T> front = node.front;
                      Node<T> newNode = new Node<>(front, element, node);
                      front.next = newNode;
                      node.front = newNode;
                      break;
                  }
                  i++;
              }
          }
          size++;
      }
  
      //删
      public void remove(T element){
          for (Node<T> node = head.next; node != null && node.element != null; node = node.next) {
              if (node.element.equals(element)){
                  Node<T> front = node.front;
                  Node<T> next = node.next;
                  front.next = next;
                  next.front = front;
              }
          }
          size --;
      }
      //改
      public void update(int index ,T element){
          int i = 0;
          for (Node<T> node = head.next; node != null && node.element != null; node = node.next) {
              if (i == index){
                  node.element = element;
              }
              i++;
          }
      }
      //查
      public int getIndex(T element){
          int i = 0;
          for (Node<T> node = head.next; node != null && node.element != null; node = node.next) {
              if (node.element.equals(element)){
                  return i;
              }
              i++;
          }
          return -1;
      }
      //包含
      public boolean contains(T element){
          for (Node<T> node = head.next; node != null && node.element != null; node = node.next) {
              if (node.element.equals(element)){
                  return true;
              }
          }
          return false;
      }
  
      @Override
      public String toString() {
          StringBuilder builder = new StringBuilder();
          for (Node<T> node = head.next; node != null&& node.element != null; node = node.next) {
              builder.append(node.toString()+" ");
          }
          return builder.toString();
      }
  }

• 测试

  public static void main(String[] args) {
          DoubleLink<String> doubleLink = new DoubleLink<>();
          doubleLink.addLast("1");
          doubleLink.addLast("2");
          doubleLink.addLast("3");
          doubleLink.addLast("4");
          System.out.println(doubleLink);
          doubleLink.addFirst("0");
          doubleLink.addFirst("-1");
          System.out.println(doubleLink);
          doubleLink.add(2,"ppp");
          doubleLink.add(0,"-2");
          System.out.println(doubleLink);
          doubleLink.remove("ppp");
          System.out.println(doubleLink);
          doubleLink.remove("0");
          System.out.println(doubleLink);
          doubleLink.remove("-1");
          System.out.println(doubleLink);
          doubleLink.remove("-2");
          System.out.println(doubleLink);
          doubleLink.update(0,"11");
          doubleLink.update(2,"33");
          System.out.println(doubleLink);
          System.out.println(doubleLink.getIndex("2"));
          System.out.println(doubleLink.getIndex("2xx"));
          System.out.println(doubleLink.contains("11"));
          System.out.println(doubleLink.contains("11x"));
      }

• 结果

  1 2 3 4
  -1 0 1 2 3 4
  -2 -1 0 ppp 1 2 3 4
  -2 -1 0 1 2 3 4
  -2 -1 1 2 3 4
  -2 1 2 3 4
  1 2 3 4
  11 2 33 4

• 只要会写这两个了,那么其他两个也就会了,好了到这就算告一段落了,如果有错,请及时评论提醒我哈!希望能给你带去帮助