链表
链表主要还是基于数组,实现起来也并不是很难,但链表的结构有很多,包括单链表,双端链表,以及双链表。这取决于构成链的节点结构。单链表只允许在表头插入数据项,而双端链表可以在表头和表尾插入数据项,但它们对于数据的变量访问都只能顺序遍历,但双向链表允许反向遍历。
在链表中,数据的插入和删除操作都很快,只需要改变一些引用的值就行了,时间复杂度为O(1), 但是查找数据并不容易,需要一次访问链表中的每一项数据(平均N/2),时间复杂度为O(N)。
注:有序数组查找(利用二分查找)数据所需时间为O(logN),插入删除数据项时,数据需要移动,这是很费时的。
实例代码实现了单链表结构,并定义了查找删除方法。
package datastructure;
public class LinkListApp {
public static void main(String[] args) {
LinkList theList = new LinkList();
theList.insertFirst(1, 10);
theList.insertFirst(2, 11);
theList.insertFirst(3, 12.0);
theList.insertFirst(4, 13.3);
theList.displayLink();
Link f = theList.find(2);
if(f != null){
System.out.println("find link with key:" + f.kData);
System.out.println("delete link with key");
theList.delete(2);
}
else
System.out.println("cant find the link");
theList.displayLink();
while(!theList.isEmpty()){
Link alink = theList.deleteFirst();
System.out.print("delete:");
alink.displayLink();
}
}
}
// 链节点
class Link{
public int kData; // 头指针
public double dData; // 数据项
public Link next; // 下个节点
public Link(int kd, double dd){
kData = kd;
dData = dd;
}
public void displayLink(){
System.out.println("{" + kData + "," + dData+ "}");
}
}
// 单端链表,只往头插入节点
class LinkList{
private Link first;
public LinkList(){
first = null;
}
public boolean isEmpty(){
return (first == null);
}
public void insertFirst(int kd, double dd){
Link newlink = new Link(kd,dd);
newlink.next = first; // newlink--->old first
first = newlink; // first--->newlink
}
public Link deleteFirst(){
Link temp = first;
first = first.next;
return temp;
}
// 查找链节点
public Link find(int key){
Link current = first;
while (current.kData != key){
if(current.next == null)
return null;
else
current = current.next;
}
return current;
}
public Link delete(int key){
Link current = first;
Link previous = first;
while(current.kData != key){
if(current.next == null){
return null;
}
else{
previous = current;
current = current.next;
}
}
// 如果是第一个,则first-->first.next;
// 否则的话,就是前一个的后一个指向当前的下一个
if(current == first){
first = first.next;
}
else {
previous.next = current.next;
}
return current;
}
public void displayLink(){
System.out.println("Link(first--->last)");
Link current = first;
while(current != null){
current.displayLink();
current = current.next;
}
System.out.println();
}
}