1、模板链表
描述
请你实现一个链表。
方法：
insert x y：将y加入链表，插入在第一个值为x的结点之前。若链表中不存在值为x的结点，则插入在链表末尾。保证x,y为int型整数。
delete x：删除链表中第一个值为x的结点。若不存在值为x的结点，则不删除。
class LinkList { //利用数组存储链表值 int[] data; //设置链表长度 int size; //设置链表头 int front = 0; //设置链表尾 int rear = 0; //链表构造器 public LinkList(int size) { data = new int[size]; } //重新tostring方法，按照想要的方式输出对象值 public String toString(){ String str=""; for(int j=0;j<rear;j++){ str+=data[j]+" "; } return str; }; public boolean isEmpty(){ return size==0?true:false; } //往链表中加元素，规则为如果链表中存在x元素，则将y插入到x之前，没有的话就插入到链表尾 public void insert(int x, int y) { //设置一个flag判断是否有x元素在数组中 int b = -1; //表明数组满了，所以要进行数组扩容 if (size == data.length) { //利用Arrays.copyof方法将满的数组赋值到新的数组，并且设置新的数组长度为原来数组长度的两倍 int[] temp = Arrays.copyOf(data, data.length * 2); //将新数组赋值给旧的数组 data = temp; //数组没满，就可以判断是否有x元素在数组内 } else { //遍历链表看是否有x元素，如果有就将元素x的位置赋值给b for (int i = 0; i < data.length; i++) { if (data[i] == x) { b = i; //找到第一个元素x的位置就退出遍历 break; } } //利用b的值判断链表中是否有x元素，如果b==-1就没有 if (b == -1) { //将尾指针的位置赋值y，并且将rear指针后移 data[rear++] = y; //链表大小+1 size++; //b不等于-1就表示链表中有x元素 } else { //遍历链表数组将b位置的元素后移一位 for (int i = rear; i > b; i--) { data[i] = data[i - 1]; } data[b] = y; rear++; size++; } } } //删除第一个指定元素 public void delete (int x) { //设置一个flag判断链表中是否有x int b = -1; //判断链表是否为空 if (size == 0) { return; } else { //遍历链表数组，看是否有x元素 for (int i = 0; i < rear; i++) { //如果存在就保存x的位置给b，然后跳出遍历 if (data[i] == x) { b = i; break; } } //判断是否操作x元素值，如果b不等于-1就表示有 if(b!=-1){ //遍历元素将元素前移动一个位置 for(int i=b;i<rear;i++){ data[i]=data[i+1]; } //尾指针-1和链表大小-1 rear--; size--; } } } }
2、思想
本次数组存储实现链表的关键是用数组来存储链表节点的值，在实现插入方法的时候要判断链表是不是已经满了，如果满了就进行扩容，就是通过扩大一倍数组，然后将原来数据存储在新的数组中，如果不是满的，那么根据要求还得判断链表中是否有x元素，如果有的话就得将y元素存储在x元素之前，这就是要求对x元素及其以后的元素要往后移动一位，如果没有的话就直接存储在链表的尾部。在实现删除的方法的时候，要判断x元素是否存在数组中，如果存在的话要对该元素后面的元素进行往前移动一位，如果不存在就不用操作。
3、节点实现链表
public static class ListNode { //节点值 public int val; //下一个节点的位置 public ListNode next; //节点构造器 public ListNode(int val){ this.val=val; } } //创建一个头结点，头结点值为-1 public static ListNode head=new ListNode(-1); //往链表插入节点 public static void insert(int x,int y){ //创建一个值为y的新节点 ListNode newNode=new ListNode(y); //将头节点赋值给名为node的节点 ListNode node=head; //设置一个标志 int sign=0; //如果node的下一个节点不是null while(null!=node.next){ //如果下一个节点的节点值是x if(node.next.val==x){ //将新建的节点的下一个节点设置为node的下一个节点 newNode.next=node.next; // node.next=newNode; //将标志设置为1，表示已经插入了 sign=1; //跳出循环 break; } //将下一个节点设置为下一次循环的节点 node=node.next; } //判断flag，如果flag==0表示上面的代码没有插入节点 if(sign==0){ //将新建的节点赋值给节点尾 node.next=newNode; } } //删除节点值为x的节点 public static void delete(int x){ //创建一个头结点 ListNode node=head; //如果下一个节点不是null的条件实现遍历链表 while(node.next!=null){ //判断下一个节点的节点值是否为x if(node.next.val==x){ //如果是的话就将node的下一个节点设置为node的下一个的下一个节点 node.next=node.next.next; //跳出循环 break; } //将node设置为下一个节点 node=node.next; } }
4、思想：本次利用节点实现链表主要是利用while语句实现对链表的遍历，在此前提是节点类要设置节点值和下一个节点，然后利用下一个节点不是null实现对链表的遍历，每次遍历最后都得将节点设置为下一个节点，在遍历也可以实现对节点值的访问。本次实现利用static将头节点固定了！！！
5、对比：数组实现和节点实现链表相比，数组实现的代码更多，也更加需要维护，链表实现的话每次加一个节点就是new了一个节点对象。个人感觉数组实心对于初学者更容易理解，但是个人推荐节点实现链表，因为数组实现插入和删除时可能要移动多个数据，节点实现的话就不需要这么麻烦。
