一、单链表

1、在我们数据结构中，单链表非常重要。它里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成，在java集合框架里面  LinkedList、HashMap（数组加链表）等等的底层都是用链表实现的。

2、下面是单链表的几个特点：

数据元素在内存中存放的地址是不连续的：单链表的结点里面还定义一个结点，它里面保存着下一个结点的内存地址，在实例化对象的时候，jvm会开辟不同内存空间，并且是不连续的。

添加效率高：添加一个元素时，先找到插入位置的前一个，只需要将1，2个元素的连接断开，将插入结点的next指向第一个元素的next

（1），然后将第一个元素的next指向插入结点（2），

不用在挪动后面元素。

删除效率高：删除一个元素时，先找到删除位置，将前一个的next指向删除位置的next，不用在挪动后面元素。

查询效率低：查询的时候必须从头开始，依次遍历，而数组因为它的内存是连续的，可以直接通过索引查找。

3、下面通过代码来实现单链表结构：

package com.tlinkedList;

/**
* User:zhang
* Date:2020/10/26
**/
public class TLinkedList<T> {
  private Node head;//链表头部
  private int size;//链表元素的个数
  public TLinkedList(){
      head=null;
      size=0;
  }
//    将结点作为内部类。也可以新建一个Node类，作为结点
  class Node{
      private Node next;//下一个结点
      private T t;//结点的数据
      public Node(T t){
          this.t=t;
      }

      public T getT() {
          return t;
      }

      public void setT(T t) {
          this.t = t;
      }
  }
//    在链表头部添加一个结点
  public void addFirst(T t){
      Node node = new Node(t);
      node.next=head;
      head=node;
      size++;
  }
//    在链表中间添加一个结点
  public void addMid(T t,int index){
      Node node = new Node(t);
      Node mid=head;
      for (int i = 0; i 1; i++) {
          mid=mid.next;
      }
      node.next=mid.next;
      mid.next=node;
      size++;
  }
//    在链表尾部添加一个结点
  public void addLast(T t){
      Node node = new Node(t);
      Node last=head;
      while (last.next!=null){
          last=last.next;
      }
      last.next=node;
      node.next=null;
      size++;
  }
//    删除链表的头结点
  public void removeFirst(){
      head=head.next;
      size--;
  }
//    删除链表的中间元素
  public void removeMid(int index){
      Node mid=head;
      if (index==0){
          removeFirst();
          return;
      }
      int j=0;
      Node qMid=head;
      while (j          qMid=mid;
          mid=mid.next;
          j++;
      }
      qMid.next=mid.next;
      size--;
  }
//    删除链表的尾结点
  public void removeLast(){
      Node mid=head;
      Node qMid=head;
      while (mid.next!=null){
           qMid=mid;
           mid=mid.next;
      }
      qMid.next= null;
      size--;
  }
//    获取链表指定下标的结点
  public Node get(int index){
      Node mid=head;
      if (index==0){
          return head;
      }
      int j=0;
      while (j          mid=mid.next;
          j++;
      }
      return mid;
  }
  public static void main(String[] args) {
      TLinkedList linkedList = new TLinkedList<>();
      linkedList.addFirst("hello1");
      linkedList.addFirst("hello2");
      linkedList.addFirst("hello3");
      for (int i = 0; i           System.out.println(linkedList.get(i).getT());
      }
//        linkedList.removeLast();
//        linkedList.removeFirst();
//        linkedList.addLast("hello4");
      linkedList.addMid("hello",2);
      System.out.println("--------------");
      for (int i = 0; i           System.out.println(linkedList.get(i).getT());
      }
  }
}

结果如下：

二、栈(Stack)

1、一提到栈我们脑海就会浮现四个字“先进后出”，没错，它就是栈的最大特点。

2、栈的应用场景也非常多，比如将字符串反转、jvm里面的栈区等等。

3、栈里面的主要操作有：

• push（入栈）：将一个数据元素从尾部插入
• pop（出栈）：将一个数据元素从尾部删除
• peek（返回栈顶元素）：将栈顶元素的数据返回
  相当于只有一个开口就是尾部，只能从尾进，从尾出。

4、下面通过链表结构实现栈结构：

package com.tStack;


/**
* User:zhang
* Date:2020/10/26
**/
public class Test_Stack<T> {
  private Node head;//栈的头结点
  private int size;//栈的元素个数
  class Node{
      private Node next;//下一个结点
      private T t;//结点的数据
      public Node