Node 类：
public class Node { public int data; public Node next=null; public Node(){ data=2147483647; next=null; } //构造函数 public Node(int data){ this.data=data; } }
MyLinkedList类
//链表操作 //1-基础 //是否空 //链表长度-用成员变量表示，增删操作同步（效果同调用函数遍历） //2-操作 //添加节点-末尾 //插入节点-索引 //根据索引删除节点 //根据值-删除节点（所有） //根据值-删除重复节点（除了第一个所有） //根据值-删除节点（第一个） //更新节点 //清空链表 //3-查询 //表中是否存在某值 //根据索引获取某一节点值 //根据值获取节点索引[数组] //根据值获取第一个节点索引 //4-遍历 //正向遍历 //反转链表 //反向遍历 //5-判断 //创建有环链表 //是否有环 //去除重复元素， //链表排序 import java.util.ArrayList; public class MyLinkedList { private int length=0; private Node head=new Node(); //构造函数默认就行，创建再添加节点 //是否空 public boolean isEmpty(){ if(this.length==0) return true; else return false; } //添加节点-末尾 public void add(int data){ Node newNode=new Node(data); Node p=this.head; //空表 if(length==0){ head.next=newNode; } //非空表 else{ //遍历至链表尾部 while(p.next!=null) p=p.next; p.next=newNode; } this.length++; } //插入节点-索引 [1-length+1] public void insert(int index,int data){ Node p=this.head; Node newNode=new Node(data); //插入位置保错 if(index<1||index>length+1){ System.out.println("插入位置出错"); } //插在末尾 else if(index==length+1){ this.add(data); } //插在表头 else if(index==1){ newNode.next=head.next; head.next=newNode; length++; } else{ //遍历到插入位置前 for(int i=0;i<index-1;i++){ p=p.next; } newNode.next=p.next; p.next=newNode; length++; } } //根据索引删除节点 public void delete(int index){ if(!isEmpty()){ //插入位置保错 if(index<1||index>length){ System.out.println("删除位置出错"); } //删除头节点 else if(index==1){ Node p=head.next; head.next=p.next; length--; } else{ //遍历至待删节点前 Node p=head; for(int i=0;i<index-1;i++){ p=p.next; } Node dp=p.next; p.next=dp.next; length--; } } else System.out.println("链表空，无法进行删除操作"); } //根据值-删除节点（所有） public void deleteall(int data){ ArrayList<Integer> indexs=getAllIndex(data); if(indexs.size()==0){ return; }else{ //从后往前删除，不用变index; for(int i=indexs.size()-1;i>=0;i--){ delete(indexs.get(i)); } } }//根据值-删除重复节点（除了第一个所有） public void deletellARepeat(int data){ ArrayList<Integer> indexs=getAllIndex(data); if(indexs.size()==0){ return; }else{ //从后往前删除，不用变index;留下index[0]即可 for(int i=indexs.size()-1;i>=1;i--){ delete(indexs.get(i)); } } } //根据值-删除节点（第一个） public void deletefirst(int data){ int index=getFirstIndex(data); if(index==-1){ return; }else{ delete(index); } } //更新节点 public void update(int index,int data){ if(!isEmpty()){ //更新位置保错 if(index<1||index>length){ System.out.println("更新位置出错"); } else if(index==1){ head.next.data=data; } else{ //遍历至更新节点 Node p=head; for(int i=0;i<index;i++){ p=p.next; } p.data=data; } }else System.out.println("链表空，无法进行更新操作"); } //清空链表 public void clear(){ head.next=null; length=0; } //表中是否存在某值 public boolean isHave(int data){ if(!isEmpty()){ Node p=head; while(p.next!=null){ p=p.next; if(p.data==data) return true; } return false; }else{ System.out.println("链表空，无数据"); return false; } } //根据索引获取某一节点值 public int getData(int index){ if(!isEmpty()){ if(index<1||index>length){ System.out.println("index出错"); return -1; } else if(index==1){ return head.next.data; } else{ //遍历至待删节点前 Node p=head; for(int i=0;i<index;i++){ p=p.next; } return p.data; } }else{ System.out.println("链表空，无数据"); return -1; } } //根据值获取节点索引[数组] public ArrayList<Integer> getAllIndex(int data){ ArrayList<Integer> indexs=new ArrayList<Integer>(); if(isHave(data)){ Node p=head; int i=0; while(p.next!=null){ p=p.next; i++; if(p.data==data) indexs.add(i); } return indexs; }else { System.out.println("链表无此数据"); ArrayList<Integer> in=new ArrayList<Integer>(); return in; } } //根据值获取第一个节点索引 public int getFirstIndex(int data){ if(isHave(data)){ //遍历到节点 Node p=head; int i=0; while(p.next!=null){ p=p.next; i++; if(p.data==data) break; } return i; }else { System.out.println("链表无此数据"); return -1; } } //正向遍历 public void print_1(){ if(!isEmpty()){ System.out.print("链表为："); Node p=head; while(p.next!=null){ p=p.next; System.out.print(p.data+"->"); } System.out.println("null"); }else System.out.println("链表空，无数据，无输出"); } //反转链表 public MyLinkedList reverse(MyLinkedList myLinkedList){ if(!isEmpty()){ if(length==1) return myLinkedList; else{ Node curNode=head.next; Node preNode=null; while(curNode!=null){ Node nextNode=curNode.next; curNode.next=preNode; preNode=curNode; curNode=nextNode; } head.next=preNode; return myLinkedList; } }else{ System.out.println("链表空，无法反转"); MyLinkedList mylist=new MyLinkedList(); return mylist; } } //反向遍历 //反转-正向遍历 //正向遍历，入栈-出栈 public void print_2(){ if(!isEmpty()){ MyLinkedList mylist1=reverse(this); MyLinkedList mylist=reverse(mylist1); System.out.print("反转"); mylist.print_1(); }else System.out.println("链表空，无数据，无输出"); } //创建有环链表 //将最后一个节点next指向前一个 public void toRinged(){ Node curNode=head; Node nextNode=curNode.next; while(curNode.next!=null&&curNode.next.next!=null){ curNode=nextNode; nextNode=nextNode.next; } nextNode.next=curNode; } //是否有环 //判断链表是否有环： //设置快指针和慢指针，慢指针每次走一步，快指针每次走两步 //当快指针与慢指针相等时，就说明该链表有环 public boolean isRinged(){ if(!isEmpty()){ if(length==1){ System.out.println("链表长度=1，无环"); return false; }else{ Node slow=head; Node fast=head; while(fast.next!=null&&fast.next.next!=null){ slow=slow.next; fast=fast.next.next; if(fast==slow) return true; } return false; } }else{ System.out.println("链表空，无环"); return false; } } //去除重复元素 public void deleteRepeatData(){ if(length<2){ System.out.println("链表长度<2，无重复数据"); }else{ MyLinkedList mylist=new MyLinkedList(); Node p=head.next; //将原链表中无重复数据添加到新链表； mylist.add(p.data); while(p.next!=null){ p=p.next; //System.out.print(p.data+" "+!mylist.isHave(p.data)+ " "); if(!mylist.isHave(p.data)) mylist.add(p.data); } //对新链表的每一个data执行this(原链表).deleteAllRepeat(data) Node p1=mylist.head; while(p1.next!=null){ p1=p1.next; //System.out.print(p1.data+" " ); this.deletellARepeat(p1.data); } } } //排序-冒泡 //交换函数 public void swip(Node p1,Node p2){ int a=p1.data; p1.data=p2.data; p2.data=a; } public void bubbleSort(){ if(length<2){ System.out.println("链表长度<2,无法排序"); }else { for(int i=1;i<length;i++){ //第一个循环，先遍历到未排序序列首部 Node p=head; for(int j=0;j<i;j++){ p=p.next; } //第二个循环比大小，交换，将最大值上浮至末尾 Node curNode=p; Node nextNode=curNode.next; if(curNode.data>nextNode.data) swip(curNode,nextNode); while(curNode.next!=null&&curNode.next.next!=null){ curNode=nextNode; nextNode=nextNode.next; if(curNode.data>nextNode.data) swip(curNode,nextNode); } //将末尾最大值放到本层循环挑出来的，未排序的首部，下层未排序首部加1 swip(p,nextNode); } } } }
验证类-test
public class linkedListTest { public static void main(String args[]) { //空？添加，正反遍历 MyLinkedList mylist=new MyLinkedList(); System.out.println("isEmpty: "+mylist.isEmpty()); mylist.add(6); mylist.add(5); mylist.add(4); mylist.add(3); System.out.println("isEmpty: "+mylist.isEmpty()); mylist.print_1(); mylist.print_2(); //插入 mylist.insert(1,14); mylist.print_1(); mylist.insert(3,14); mylist.print_1(); mylist.insert(17,14); mylist.print_1(); //删除 mylist.delete(0); mylist.print_1(); mylist.delete(4); mylist.print_1(); mylist.delete(17); mylist.print_1(); //删除重复我-前提：获取index数组 //mylist.deleteall(14); // mylist.deletellARepeat(14); mylist.deletefirst(14); mylist.print_1(); //更新 mylist.update(2,144); mylist.print_1(); mylist.update(0,144); mylist.print_1(); mylist.update(17,144); mylist.print_1(); //清空 //mylist.clear(); // mylist.print_1(); //get System.out.println(mylist.getData(0)); System.out.println(mylist.getData(3)); System.out.println(mylist.getData(17)); //成环 // mylist.toRinged(); // System.out.println("isRinged: "+mylist.isRinged()); // mylist.print_1(); //去重复 MyLinkedList mylist2=mylist; mylist2.add(6); mylist2.add(6); mylist2.add(17); mylist2.add(17); mylist2.add(8); mylist2.add(8); mylist2.print_1(); mylist2.deleteRepeatData(); mylist2.print_1(); //排序 mylist2.bubbleSort(); mylist2.print_1(); } }