链表是物理存储单元上非连续的，非顺序的存储结构，由一系列节点组成。

单向链表的实现

实例代码

function LinkList() {
	//	定义节点
	var Node = function(data) {
			this.data = data;
			this.next = null;
		}
	var length = 0; //	⻓度
	var head = null; //	头节点
	var tail = null; //	尾节点
	//	添加⼀个新元素
	this.append = function(data) {
		//	创建新节点
		var node = new Node(data);
		//	如果是空链表
		if (head == null) {
			head = node;
			tail = head;
		} else {
			tail.next = node; //	尾节点指向新创建的节点
			tail = node; //	tail指向链表的最后⼀个节点
		}
		length += 1; //	⻓度加1
		return true;
	};
	//	返回链表⼤⼩
	this.length = function() {
		return length;
	};
	//	在指定位置插⼊新的元素
	this.insert = function(index, data) {
		if (index == length) {
			return this.append(data);
		} else if (index > length || index < 0) {
			return false;
		} else {
			var new_node = new Node(data);
			if (index == 0) {
				new_node.next = head;
				head = new_node;
			} else {
				var insert_index = 1;
				var curr_node = head;
				//	找到应该插⼊的位置
				while (insert_index < index) {
					curr_node = curr_node.next;
					insert_index += 1;
				}
				var next_node = curr_node.next;
				curr_node.next = new_node;
				new_node.next = next_node;
			}
			length += 1;
			return true;
		}
	};
	//	删除指定位置的节点
	this.remove = function(index) {
		if (index < 0 || index >= length) {
			return null;
		} else {
			var del_node = null;
			if (index == 0) {
				// head指向下⼀个节点
				del_node = head;
				head = head.next;
			} else {
				var del_index = 0;
				var pre_node = null;
				var curr_node = head;
				while (del_index < index) {
					del_index += 1;
					pre_node = curr_node;
					curr_node = curr_node.next;
				}
				del_node = curr_node;
				pre_node.next = curr_node.next;
				// 如果删除的是尾节点
				if (curr_node.next == null) {
					tail = pre_node;
				}
			}
			length -= 1;
			del_node.next = null;
			return del_node.data;
		}
	};
	// 删除尾节点
	this.remove_tail = function() {
		return this.remove(length - 1);
	};
	// 删除头节点
	this.remove_head = function() {
		return this.remove(0);
	};
	// 返回指定位置节点的值
	this.get = function(index) {
		if (index < 0 || index >= length) {
			return null;
		}
		var node_index = 0;
		var curr_node = head;
		while (node_index < index) {
			node_index += 1;
			curr_node = curr_node.next;
		}
		return curr_node.data;
	};
	// 返回链表头节点的值
	this.head = function() {
		return this.get(0);
	}
	// 回链表尾节点的值
	this.tail = function() {
		return this.get(length - 1);
	}
	// 返回指定元素的索引,如果没有,返回-1，有多个相同元素,返回第⼀个
	this.indexOf = function(data) {
		var index = -1;
		var curr_node = head;
		while (curr_node) {
			index += 1
			if (curr_node.data == data) {
				return index;
			} else {
				curr_node = curr_node.next;
			}
		}
		return -1;
	};
	//	输出链表
	this.print = function() {
		var curr_node = head;
		var str_link = ""
		while (curr_node) {
			str_link += curr_node.data.toString() + "	->";
			curr_node = curr_node.next;
		}
		str_link += "null";
		console.log(str_link);
		console.log("⻓度为" + length.toString());
	};
	//	isEmpty
	this.isEmpty = function() {
		return length == 0;
	};
	//	清空链表
	this.clear = function() {
		head = null;
		tail = null;
		length = 0;
	};
};

链表的应用

1. 快乐数 - LeetCode连接 (opens new window)

   编写一个算法来判断一个数 n 是不是快乐数。
   - 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
   - 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
   - 如果 可以变为  1，那么这个数就是快乐数。
   - 如果 n 是快乐数就返回 true ；不是，则返回 false 。
   

   实例代码

   class Solution {
   	public boolean isHappy(int n) {
   		int p = n;
   		int q = n;
   		do {
   			p = getNext(p);
   			q = getNext(getNext(q));
   		} while (p!=q && q != 1);
   		return q==1;
   	}
   	public int getNext (int x){
   		int z = 0;
   		while(x != 0){
   			z += (x % 10) * (x % 10);
   			x /= 10;
   		}
   		return z;
   	}
   }