[数据结构与算法]Java——单链表队列

单链表队列

首先，我们通过一张图还直观的显示出链表的作用。

头节点是不存数据的，只是有一个指针，为了方便我们找到我们链表的第一个元素，链表中是通过指针来找到下一个元素的，所以添加和删除元素很方便，不需要像数组那样复制，节省了很大的内存空间。最后一个节点是没有指针的也就是null 。

我们把每一个元素看做成一个节点，节点中有数据和指向下一个节点的指针，所以一般我们需要创建两个类。

节点类：

package xq0825;

public class Node {
 Node next; //下一个节点
 int data;
 
 public Node(){
  
 }
 public Node(int data ,Node next) {
  
  this.data=data;
  this.next=next;
 }
}

链表类：

package xq0825;

public class LinkList {
 Node head;  //定义头节点 ，只有指针没数据，找到链表的入口
 int size;
 
 public LinkList() {
  //初始化头结点
  this.head=new Node();
  //初始化元素个数
  this.size =0;
 }
 
 //清空链表
 public void cleatr() {
  head.next=null;
  this.size=0;
 }

 //获取链表的长度
 public int length() {
  
  return size;
 }
 
 //判断链表是否为空
 public boolean isEmpty() {
  return size==0;
 }
 
 //获取指定位置的元素
 public int get(int i) {
  
  //从头结点开始往后找，直到找到第i个节点
  Node n=head.next;
  for (int index =0;index <i; index++) {
   n=n.next;
  }
  return n.data;
 }
 
 //向链表中添加元素
 public void add(int data) {
  //找到最后一个节点
  Node n=head;
  
  while(n.next!=null) {
   n=n.next;
  }
  
  //创建一个新节点，保存我们要添加的元素
  Node newNode = new Node(data,null);
  
  //让尾节点指向新节点  
  n.next=newNode;
  
  //元素个数加1 
  size++;
 }
 
 //向指定位置添加元素
 public void add(int i,int data) {
  //找到i 位置的前一个节点
  Node n =head;
  for(int index=0; index<i-1;index++) {
   n=n.next;
  }
  
  //找到i 位置的节点
  Node n1 =n.next;
  
//  Node n1 =head;
//  for(int index=0; index<i-1;index++) {
//   n1=n1.next;
//  }
  
  //创建一个新节点，指向i 位置的节点
  Node newNode=new Node (data,n1);
//  Node newNode = new Node(data,null);
//  newNode.next=n1;
  
  //让i 位置前一个节点指向新节点
  n.next=newNode;
  
  size++;
 }
 
 //删除指定位置的元素，并返回删除的元素 
 public int remove(int i) {
  //找到i 位置的前一个节点
  Node n =head;
  for(int index=0; index<i-1;index++) {
   n=n.next;
  }
  //找到i 位置的节点
  Node n1 =n.next;
  //找到i位置的下一个节点
  Node n2 =n1.next;
  //让i 位置的前一个节点指向 i位置的下一个节点
  n.next=n2;
  
  size--;
  
    
  return n1.data;
 }
 
 //查找出元素在链表中第一次出现的位置
 public int indexOf(int data) {
  //从头结点开始 找到每一个节点与data比较
  Node n =head;
  for(int i=0; n.next!=null;i++) {
   n=n.next;
   if(n.data ==data) {
    return i;
   }
  }
  //返回-1 代表链表中没有这个元素
  return -1;
 }
 public static void main(String[] args) {
  LinkList list = new LinkList();
  list.add(1);
  list.add(2);
  list.add(3);
  
  
   System.out.println(list.indexOf(1));
   list.remove(0);
   System.out.println(list.indexOf(1));
  }
}

输出的结果为：

0
-1