本文共 6611 字，大约阅读时间需要 22 分钟。
1.链接点
链接点核心思想：
链接点中包含一个数据域和一个指针域。其中数据域用来包装数据，而指针域用来指向下一个链接点。 链接点模型：package cn.deu;public class Link { //数据域 private long data; //指针域 private Link next; public Link(long data) { this.data = data; } public long getData() { return data; } public void setData(long data) { this.data = data; } public Link getNext() { return next; } public void setNext(Link next) { this.next = next; } } 链接点测试： package en.edu.Test;import cn.deu.Link;public class TestLink { public static void main(String[] args) { Link link1=new Link(10); Link link2=new Link(45); Link link3=new Link(360); Link link4=new Link(1); link1.setNext(link2); link2.setNext(link3); link3.setNext(link4); System.out.println(link1.getData()); System.out.println(link1.getNext().getData()); System.out.println(link1.getNext().getNext().getData()); System.out.println(link1.getNext().getNext().getNext().getData()); }}结果：10453601 2.链表
链表核心思想：
链表中只包含一个数据项，即对第一个链接点的引用 链表模型：package cn.deu;//其实java的指针就是"引用"而已public class LinkList { private Link first=new Link(-1); //思路：一个首链接点，每添加一个新链接点 //将新链接点的指针指向首链接点的指针所指向的对象 //之后将首链接点的指针指向新连接点对象 public void insert(long value){ Link link1=new Link(value); if(first.getNext()==null){ first.setNext(link1); }else{ link1.setNext(first.getNext()); first.setNext(link1); } } public void displayAll(){ Link current =first; while(current.getNext()!=null){ if(current!=first){ System.out.println("当前数据："+current.getData()); } System.out.println("链接的下一个数据"+current.getNext().getData()); current=current.getNext(); } }} 链表测试类： package en.edu.Test;import cn.deu.LinkList;public class TestLinkList { public static void main(String[] args) { LinkList linklist=new LinkList(); linklist.insert(1); linklist.insert(5); linklist.insert(6); linklist.insert(9); linklist.displayAll(); }}/* * 结果： 链接的下一个数据9当前数据：9链接的下一个数据6当前数据：6链接的下一个数据5当前数据：5链接的下一个数据1 */ 3.查找指定节点
模型：
package cn.deu;//其实java的指针就是"引用"而已public class LinkList { private Link first=new Link(-1); //思路：一个首链接点，每添加一个新链接点 //将新链接点的指针指向首链接点的指针所指向的对象 //之后将首链接点的指针指向新连接点对象 public void insert(long value){ Link link1=new Link(value); if(first.getNext()==null){ first.setNext(link1); }else{ link1.setNext(first.getNext()); first.setNext(link1); } } public void displayAll(){ Link current =first; while(current.getNext()!=null){ if(current!=first){ System.out.println("当前数据："+current.getData()); } System.out.println("链接的下一个数据"+current.getNext().getData()); current=current.getNext(); } } //查找节点 public Link find(long key){ Link current=first.getNext(); while(current.getData()!=key){ if(current.getNext()==null){ return null; } current=current.getNext(); } return current; }} 测试： package en.edu.Test;import cn.deu.LinkList;public class TestLinkList { public static void main(String[] args) { LinkList linklist=new LinkList(); linklist.insert(1); linklist.insert(5); linklist.insert(6); linklist.insert(9); if(linklist.find(5)!=null){ System.out.println("找到节点，数据为:"+linklist.find(5).getData()); } }} 结果：找到节点，数据为:5
4.添加指定节点
思路：
插入节点到指定位置（insert方法重载）， 新加入的节点的下一个是原来节点的下一个， 当前节点的下一个设为新加入的。public void insert(long value,int pos){ boolean flag=true; Link current=first.getNext(); while(current.getData()!=pos){ if(current.getNext()==null){ flag=false; System.out.println("插入失败"); break; } current=current.getNext(); } if(flag==true){ Link InsertNum=new Link(value); //新加入的节点的下一个是原来节点的下一个 InsertNum.setNext(current.getNext()); //当前节点的下一个设为新加入的 current.setNext(InsertNum); System.out.println("插入成功！"); }} 测试： package en.edu.Test;import cn.deu.LinkList;public class TestLinkList { public static void main(String[] args) { LinkList linklist=new LinkList(); linklist.insert(1); linklist.insert(5); linklist.insert(6); linklist.insert(9); linklist.displayAll(); /* * 结果： 链接的下一个数据9 当前数据：9 链接的下一个数据6 当前数据：6 链接的下一个数据5 当前数据：5 链接的下一个数据1 */ //将数据插入到5后面 linklist.insert(10, 5); linklist.displayAll(); System.out.println("-------------------------"); //将数据插入到110后面(没有110，会失败) linklist.insert(10, 110); linklist.displayAll(); /* * 结果： 插入成功！ 链接的下一个数据9 当前数据：9 链接的下一个数据6 当前数据：6 链接的下一个数据5 当前数据：5 链接的下一个数据10 当前数据：10 链接的下一个数据1 ------------------------- 插入失败 链接的下一个数据9 当前数据：9 链接的下一个数据6 当前数据：6 链接的下一个数据5 当前数据：5 链接的下一个数据10 当前数据：10 链接的下一个数据1 */ }} 5.删除指定节点 //删除节点//思路：将要删除节点的前一个节点的next指向要删除节点的nextpublic void delete(long key){ boolean flag=true; Link current=first.getNext(); while(current.getNext()!=null&¤t.getNext().getData()!=key){ current=current.getNext(); if(current.getNext()==null){ flag=false; System.out.println("删除失败！"); break; } } if(flag==true){ current.setNext(current.getNext().getNext()); //中间那个节点被丢掉后，Java的垃圾回收器就会自动回收 System.out.println("删除成功！"); } } 测试： package en.edu.Test;import cn.deu.LinkList;public class TestLinkList { public static void main(String[] args) { LinkList linklist=new LinkList(); linklist.insert(1); linklist.insert(10); linklist.insert(5); linklist.insert(6); linklist.insert(9); linklist.displayAll(); System.out.println("-------------------------"); linklist.delete(10); linklist.displayAll(); System.out.println("-------------------------"); linklist.delete(110); linklist.displayAll(); }}结果： 链接的下一个数据9 当前数据：9 链接的下一个数据6 当前数据：6 链接的下一个数据5 当前数据：5 链接的下一个数据10 当前数据：10 链接的下一个数据1 ------------------------- 删除成功！ 链接的下一个数据9 当前数据：9 链接的下一个数据6 当前数据：6 链接的下一个数据5 当前数据：5 链接的下一个数据1 ------------------------- 删除失败！ 链接的下一个数据9 当前数据：9 链接的下一个数据6 当前数据：6 链接的下一个数据5 当前数据：5 链接的下一个数据1 6.比较链表与顺序表
package en.edu.Test;import java.text.SimpleDateFormat;import java.util.Date;import cn.deu.LinkList;import cn.deu.MyArray;public class TestLinkAndList { public static void main(String[] args) { //构建链表 Date date1=new Date(); LinkList linkList=new LinkList(); for (int i = 0; i < 100000; i++) { linkList.insert(i); } Date date2=new Date(); System.out.println(date2.getTime()-date1.getTime()); //构建顺序表（从小到大） date1=new Date(); MyArray ma=new MyArray(100000); for (int i = 0; i < 100000; i++) { ma.insert(i); } date2=new Date(); System.out.println(date2.getTime()-date1.getTime()); date1=new Date(); linkList.delete(11111); date2=new Date(); System.out.println(date2.getTime()-date1.getTime()); date1=new Date(); ma.delete(11111); date2=new Date(); System.out.println(date2.getTime()-date1.getTime()); }} 结果： 26 4367 删除成功！ 13 45 对比结果： 链表进行插入删除比较快捷，但是查找比较慢 顺序表查找起来和修改起来比较好，但是插入删除比较慢。 比如公司的职员表经常发生变化，最好使用链表，因为插入删除比较快捷。 若表是固定的，就使用顺序表即可。 转载请注明出处：