4.向指定位置i处插入元素t
//向指定位置i处添加元素 public void insert(int i,T t){ //找到i位置前一个结点 Node pre=head; for(int j=0;j<=i-1;i++){ pre=pre.next; } //找到i位置的结点 Node curr =pre.next; //创建新节点,并且新结点需要指向原来i位置的结点 Node newNode=new Node(t,curr); //原来i位置的前一个节点指向新结点即可 pre.next=newNode; N++; }
解析:在指定位置插入元素，类似我们上面在结尾添加元素，但插入时我们不仅要让i位置前一个结点next新节点，还要让新结点的next指向i位置后一个结点。我们先通过遍历找到i位置的前一个结点并记录为pre，此时我们pre.next就是我们i位置处的结点，我们保存为curr。这时我们创建新节点newNode，它的数据域为t，指针域为我们的curr，也就是原来i位置上的结点，这时我们再让pre指向newNode就完成了我们的插入操作。可以看看下面的图解步骤
对于指定位置的插入操作，顺序表需要对大量的元素进行移动，效率很低，如果你想在下标为0处插入，甚至需要整个数组进行后移。而链表相对于顺序表最显著的优点就在这，它在插入时完全不需要考虑移动元素，因为它的地址是不连续的，它可以在任意地方开辟空间生成结点。
5.删除指定位置i处的元素，并返回该元素
//删除指定位置处i处的元素,并返回被删除的元素 public T remove(int i){ Node pre=head; //先找到i处前一个结点 for (int j = 0; j <= i - 1; j++) { pre=pre.next; } //记录i处的结点 Node n=pre.next; //让i处前一个结点指向i处后一个结点 pre.next=n.next; N--; return n.item; }
解析：删除的操作很简单，我们同样通过遍历得到i处的前一个元素并记录为pre，再将pre.next也就是i处的结点记录为n。然后我们让n.next赋值给pre.next，也就是让i处前一个结点（pre）指向i处后一个结点
下面为简易图解
6.查找元素第一次出现的位置
//查找元素第一次出现的位置 public int indexOf(T t){ Node pre=head; for (int i = 0;pre.next!=null; i++) { pre=pre.next; if(pre.item==t) return i; } return -1; }
解析：从头开始遍历，每次判断是否是我们需要查找的结点，如果是直接返回，如果遍历完仍未找到，则返回-1，表示链表中没有需要查找的元素。
7.反转链表
该内容为补充内容，反转链表不属于链表的功能，但我们也需要了解，技多不压身。
//用来反转整个链表 public void reverse(){ //判断当前链表是否为空，如果为空则结束运行 if(isEmpty()) return; reverse(head.next); } //反转指定的某个结点 public Node reverse(Node curr){ if(curr.next==null){ head.next=curr; return curr; } //递归的反转当前结点curr的下一个结点，返回值就是链表反转后，当前结点的上一个结点 Node pre=reverse(curr.next); //让返回的结点的下一个结点变为当前结点curr pre.next=curr; //把当前的下一个结点变为null curr.next=null; return curr; }
解析：这个代码最好通过debug一步步去理解它，它会在Node pre=reverse(curr.next)这个地方一直进入循环，因为要满足if循环中的某个结点curr.next为null，那么只有链表中的最后一个结点，此时让头结点指向它，也就是下图中的第一次递归完的情况。但我们要清楚在我们将最后一个结点传入这个方法时，此时是在倒数第二个结点为curr的情况下，因为此时curr这个结点在这个方法体中，在if判断中它不成立，因为它后面还有链表最后一个结点，前面的结点也是如此，所以if判断条件都不通过，但此时curr传入它的next进入循环后，我们姑且称之为尾结点，尾结点在if判断中是成立的，它在完成反转后，也就是让头结点指向它后，将自己返回。这时尾结点被一个pre接收，然后pre.next=curr，也就是让最后一个结点指向倒数第二个结点，接着将倒数第二个结点返回，然后继续递归，如图：
总结：单链表和顺序表一样属于基础数据结构，需要我们掌握并熟悉它的功能，反转链表部分我的表达可能不是很清楚，不明白的同学可以自己画图一步步debug，毕竟数据结构很抽象，需要我们画图才更易理解
