链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。
连接点：
[java]
package ch04Link;
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 ch04Link;
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;
}
}
测试连接点：
[java]
package ch04Link;
public class TestLink {
public static void main(String[] args) {
Link link1 = new Link(10);
Link link2 = new Link(50);
Link link3 = new Link(20);
Link link4 = new Link(100);
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());
}
}
package ch04Link;
public class TestLink {
public static void main(String[] args) {
Link link1 = new Link(10);
Link link2 = new Link(50);
Link link3 = new Link(20);
Link link4 = new Link(100);
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());
}
}
链表：
[java]
package ch04Link;
/**
* 链表：核心思想：链表中只包含一个数据项，即对第一个连接点的引用
* @author hadoop
*
*/
public class LinkList {
private Link first;
// 插入
public void insert(long value){
Link link = new Link(value);
if(first == null)
first = link;
else{
link.setNext(first);
first = link;
}
}
// 打印链表
public void display(){
Link current = first;
while(current != null){
System.out.print(current.getData() + " ");
current = current.getNext();
}
}
// 查询链表
public Link find(long key){
Link current = first;
while(current.getData() != key){
if(current.getNext() == null)
return null;
current = current.getNext();
}
return current;
}
// 插入节点到指定位置
public void insert(long value, int pos){
if(pos == 0)
insert(value);
else{
Link current = first;
for(int i = 0; i < pos - 1; i++)
current = current.getNext();
Link link = new Link(value);
link.setNext(current.getNext());
curr