Java数据结构（链表篇） - JAVA

ent.setNext(link);
}
}

// 删除节点
public void delete(long value){
Link current = first;
Link ago = first;
while(current.getData() != value){
if(current.getNext() == null)
return;
else{
ago = current;
current = current.getNext();
}
}
if(current == first)
first = first.getNext();
else
ago.setNext(current.getNext());
}
}

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());
current.setNext(link);
}
}

// 删除节点
public void delete(long value){
Link current = first;
Link ago = first;
while(current.getData() != value){
if(current.getNext() == null)
return;
else{
ago = current;
current = current.getNext();
}
}
if(current == first)
first = first.getNext();
else
ago.setNext(current.getNext());
}
}

测试：

[java]
package ch04Link;

public class TestLinkList {

public static void main(String[] args) {
LinkList linkList = new LinkList();

linkList.insert(20);
linkList.insert(80);
linkList.insert(40);
linkList.insert(60);
linkList.display();
System.out.println();

System.out.println("找到节点，数据为：" + linkList.find(80).getData());

linkList.insert(100, 0);
linkList.display();

System.out.println();

linkList.delete(80);
linkList.display();
}
}

package ch04Link;

public class TestLinkList {

public static void main(String[] args) {
LinkList linkList = new LinkList();

linkList.insert(20);
linkList.insert(80);
linkList.insert(40);
linkList.insert(60);
linkList.display();
System.out.println();

System.out.println("找到节点，数据为：" + linkList.find(80).getData());

linkList.insert(100, 0);
linkList.display();

System.out.println();

linkList.delete(80);
linkList.display();
}
}

比较链表和顺序表：

[java]
package ch04Link;

import ch01Array.MyArray;

public class Test {

public static void main(String[] args) {
// 构造链表
long date1 = System.currentTimeMillis();
LinkList linkList = new LinkList();
for(int i = 0; i < 1000000; i++)
linkList.insert(i);
long date2 = System.currentTimeMillis();
System.out.println(date2 - date1);

// 构造顺序表
long date3 = System.currentTimeMillis();
M

Java数据结构（链表篇） (二)