综合网上实例
参考：
http://www.2cto.com/kf/201204/126773.html JavaScript实现参考
http://m.blog.csdn.net/blog/caiwenfeng_for_23/8496029 Java实现参考
JS实现
function linkNode(_key, _value){ // 链表类的节点类
this.Key = _key;
this.Value = _value;
this.next = null;
}
function Link(){ /// 创建一个链表类
this.root = new linkNode(null, null); //root永远是个空节点
this.end = this.root;
}
Link.prototype ={
count: 0,
value: function (_key) { /// 根据key的值来获取value值
var i = this.root;
while (Boolean(i = i.next)) {
if (i.Key == _key)
return i.Value;
}
},
add: function (_key, _value){ /// 往链表的尾部中加入一个节点
var i = this.root;
while (Boolean(i = i.next)){
if (i.Key == _key)
return i.Value = _value;
}
var node = new linkNode(_key, _value);
if (this.count == 0)
this.root.next = node;
else
this.end.next = node;
this.end = node;
this.count++;
return _value;
},
insert: function (_key, node){ /// 从链表类的某节点之后插入新节点node.
var i = this.root;
while (Boolean(i = i.next)){
if (i.Key == _key) {
var tmp = i.next;
i.next = node;
node.next = tmp;
break;
}
}
},
insertBefore: function (_key, node) { /// 从链表类的某节点之后插入新节点node.
var i = this.root;
while (Boolean(i = i.next)){
if (i.next.Key == _key){
var tmp = i.next;
i.next = node;
node.next = tmp;
break;
}
}
},
remove: function (_key){ /// 从链表类中移除一个key
var i = this.root;
do {
if (i.next.Key == _key) {
if (i.next.next == null)
this.end = i;
i.next = i.next.next;
this.count--;
return;
}
} while (Boolean(i = i.next))
},
exists: function (_key){ /// 检查链表类中是否存在一个key
var i = this.root;
while (Boolean(i = i.next))
if (i.Key == _key)
return true;
return false; },
removeAll: function (){ /// 清空链表类
this.root = new linkNode(null, null);
this.end = this.root;
this.count = 0;
},
Obj2str: function (o) {
if (o == undefined)
{
return "";
}
var r = [];
if (typeof o == "string")
return "\"" + o.replace(/([\"\\])/g, "\\$1").replace(/(\n)/g, "\\n").replace(/(\r)/g, "\\r").replace(/(\t)/g, "\\t") + "\""; if (typeof o == "object") { if (!o.sort) { for (var i in o) r.push("\"" + i + "\":" + this.Obj2str(o[i])); r = "{" + r.join() + "}"; } else{ for (var i = 0; i < o.length; i++) r.push(this.Obj2str(o[i])) r = "[" + r.join() + "]"; } return r; } return o.toString().replace(/\"\:/g, '":""'); }, getJSON: function () { /// 转换成JSON字符串 var me = this; var getChild = function (node){ var str = ""; str += "{\"Key\":\"" + node.Key + "\",\"Value\":" + me.Obj2str(node.Value); if (node.next != null) str += ",\"next\":" + getChild(node.next); else str += ",\"next\":\"null\""; str += "}"; return str; }; var link = "{\"root\":{\"Key\":\"null\",\"Value\":\"null\",\"next\":"; if (this.count == 0)//如果空表 { return "{\"root\":{\"Key\":\"null\",\"Value\":\"null\",\"next\":\"null\"},\"end\":{\"Key\":\"null\",\"Value\":\"null\",\"next\":\"null\"},\"count\":\"0\"}"; } link += getChild(this.root.next) + "}"; //加上end link += ",\"end\":{\"Key\":\"" + this.end.Key + "\",\"Value\":" + me.Obj2str(this.end.Value) + ",\"next\":\"null\""; link += "},\"count\":\"" + this.count + "\"}"; return link; }, getArrayJSON: function (){ /// 转所有节点的value换成JSON字符串,数组格式 var link = "{\"link\":["; var i = this.root; while (Boolean(i = i.next)){ link += this.Obj2str(i.Value) + ","; } link = link.substr(0, link.length - 1); link += "]}"; return link; }, sort: function (fn){ /// 对链表进行排序 /// 比较两个链表元素大小的方法，当返回真时，此方法的参数所指的节点将往下沉 if (fn != null){ var i = this.root; while (Boolean(i = i.next)){ var j = this.root; while (Boolean(j = j.next)){ if (j.next != null) { if (fn.call(this, j)){ var Key = j.Key; var Value = j.Value; j.Key = j.next.Key; j.Value = j.next.Value; j.next.Key = Key; j.next.Value = Value; } } } this.end = i; } } else {
}
}};
Java实现
public class LinkList<T> {
public class Node{ //定义节点
private T data;
private Node next;
public Node(){
}
public Node(T data,Node next){
this.data=data;
this.next=next;
}
}
private Node header;//头节点
private Node tail;//尾节点
private int size;//链表大小
//构造函数初始化数据
public LinkList(){
header=null;
tail=null;
}
public LinkList(T element){
header=new Node(element,null);
tail=header;
size++; }
//链表长度
public int length(){
return size;
}
//返回指定位置index的节点
public T get(int index){
return getNodeByIndex(index).data;
}
private Node getNodeByIndex(int index) {
if(index<0||index>size-1){
throw new IndexOutOfBoundsException("线性表索引越界");
}
Node current=header;
for(int i=0;i<size&¤t!=null;i++,current=current.next){
if(i==index){
return current;
}
}
return null;
}
//返回element在链表的位置，-1表示不存在
public int locate(T element){
Node current=header;
for(int i=0;i<size&¤t!=null;i++,current=current.next){
if(current.data==element){
return i;
}
}
return -1;
}
//在index位置插入节点element
public void insert(T element,int index){
if(index<0||index>size){
throw new IndexOutOfBoundsException("线性表索引越界");
}
if(header==null){
add(element);
}else{
if(index==0){
addAtHeader(element);
}else{
Node prev=getNodeByIndex(index-1);
prev.next=new Node(element,prev.next);
size++;
}
}
}
//采用尾插法为链表添加新节点 private void add(T element) { if(header==null){
header=new Node(element,null);
tail=header;
}else{
Node newNode=new Node(element,null);
tail.next=newNode;
tail=newNode;
}
size++;
}
//采用头插法为链表添加新节点
private void addAtHeader(T element){
header=new Node(element,header);
if(tail==null){
tail=header;
}
size++;
}
//删除index位置的节点
public T delete(int index){
if(index<0||index>size-1){
throw new IndexOutOfBoundsException("线性表索引越界");
}
Node del=null;
if(index==0){
del=header;
header=header.next;
}else{
Node prev=getNodeByIndex(index-1);
del=prev.next;
prev.next=del.next;
del.next=null;
}
size--;
return del.data;
}
//从链表后面删除一个节点
public T remove(){
return delete(size-1);
}
//是否为空
public boolean empty(){
return size==0;
}
//清空链表
public void clear(){
header=null;
tail=null;
size=0;
}
public String toString(){
if(empty()){
return "[]";
}else{
StringBuilder sb=new StringBuilder("[");
for(Node current=header;current!=null;current=current.next){
sb.append(current.data.toString()+", ");
}
int len=sb.length();
return sb.delete(len-2, len).append("]").toString();
}
}
public static void main(String[] args) {
LinkList<String> list=new LinkList<String>();
list.insert("aaa", 0);
list.add("bbb");
list.add("ccc");
System.out.println(list.toString());
list.insert("ddd", 1);
System.out.println(list.toString());
list.delete(2);
System.out.println(list.toString());
System.out.println("ccc在链表中的位置："+list.locate("ccc"));
System.out.println("链表中索引2处的元素："+list.get(2));
}
}
