单链表——基本操作（求表长、查找、插入、删除）(java)

public class LinkedList { public Node first;//定义头结点 public LinkedList(){ this.first=null; } //定义节点类 public class Node{ int data; Node next=null; public Node(int data){ this.data=data; } } //求表长，时间性能为O(n) public int Length(Node first){ Node p=first; //p指向表的第一个节点 int j=0; while(p!=null){ p=p.next; j++; //当前p指向的是第j个结点 } return j; } //查找第K个元素(按位置查找)，平均时间性能为O(n) public Node FindKth(int K,Node first){ Node p=first; int i=1; while(p!=null&&i<K){ p=p.next; i++; } if(i==K) return p; else return null; } //查找元素K（按值查找），平均时间性能为O(n) public Node Find(int K,Node first){ Node p=first; while(p!=null&&p.data!=K){ p=p.next; } return p; } //在第i个结点插入（即在第i-1(1<=i<=n+1)个结点后）插入一个值为X的新结点, public Node insert(int i,int X,Node first){ Node p,node; if(i==1){ //新结点插在表头 node=new Node(X); node.next=first; return node; } p=FindKth(i-1,first); if(p==null){ System.out.println("参数i错"); return null; }else{ node=new Node(X); node.next=p.next; //新结点插入在第i-1个结点的后面 p.next=node; //注意这一句和上一句的先后顺序，不能交换 return first; } } //删除链表的第i(1<=i<=n)个位置上的结点 public Node delete(int i,Node first){ Node p,node; if(i==1){ //若要删除的是表的第一个结点 node=first; //node指向第一个结点 if(first!=null) //从链表中删除 first=first.next; else return null; return first; } p=FindKth(i-1,first); //平均查找次数为n/2，平均时间性能O(n) if(p==null){ System.out.println("第"+(i-1)+"个节点不存在"); return null; } else if(p.next==null){ System.out.println("第"+i+"个节点不存在"); return null; } else{ node=p.next; //node指向p的下一个结点 p.next=node.next; } return first; } }