链表是一种非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个组成单元称为结点）组成，每个结点包括两个部分：存储在该节点的数据和指向下一个节的指针。起始节点称为头结点（head), 最后一个节点的下一个节点为空，其包含的指针指向null。

链表的特点

• 链表非连续存储结构，可以动态调整链表大小，节省了存储空间

链表的分类

常见的链表结构分为以下几类:

• 单链表
• 双链表
• 循环单向链表
• 循环双向链表

单链表

单链表是最基础的一种链表结构，每个节点(Node)只包含了两个基础数据,数据和下一个节点指针。

我们先设计实现单链表, 单链表结构中包含两个数据类型：节点类(Node), 链表类(LinkList)。

Node类

节点类负责存储数据和一个指向下一个节点的指针：

function Node = function(data) {
	this.data = data; // 存储的数据
	this.next = null; // 指向下一个节点指针
}

LinkList类

LinkList类负责管理操作节点，例如：添加节点、删除节点、搜索节点、遍历节点等。其构造函数如下:

function LinkList() {
	this.head = null; // 头结点
	this.length = 0; // 记录节点长度
}

添加节点一般有几种实现方式：追加（append)节点(在尾部添加节点）和指定位置插入(insert)节点。

追加节点

追加节点是在链表尾部直接加入一个新的节点，当链表没有节点时，先需要创建一个头结点，否则就顺着节点指针，移动到最后一个节点，将当前链表最后一个节点的指针指向新的节点。

this.append = function(data) {
	var node = new Node(data);
	if (this.head == null) {
		this.head = node;
	} else {
		var current = this.head;
		var previous;
		while(current) {
			previous = current;
			current = current.next;
		}
		previous.next = node;
	}
	this.length++;
}

插入节点

插入节点是在指定位置插入一个新的节点，但是插入位置不能超过当前节点的长度。插入时，要需要先移动到链表指定插入位置:

this.insert = function(pos, data) {
	var node = new Node(data);

	if (pos > -1 && pos < length) {
		// 如果插在头结点
		if (pos == 0) {
			node.next = this.head;
			this.head = node;
		} else {
			var current = this.head;
			var previous;
			var index = 0;
			while(index++ < pos) {
				previous = current;
				current = current.next;
			}

			previous.next = node;
			node.next = current;
		}
		

		this.length++;
		return true;
	} 
	return false;
}

删除节点

删除指定位置的节点，需要先移动到指定位置的上一个节点，将上一个节点的指针指向当前位置的下一个节点。

this.removeAt = function(pos) {
	if (pos > -1 && pos < length) {
		var current = this.head;
		var previous;
		var index = 0;
		while(index++ < pos) {
			previous = current;
			current = current.next;
		}

		previous.next = current.next;

		this.length--;
		return true;
	} 

	return false;
}

搜索节点

将每个节点的存储数据和给定元素匹配，如果匹配成功则返回节点，否则返回null。

this.search = function(data) {
	if (data) {
		var current = this.head;
		
		while (current) {
			if (current.data == data) {
				return current;
			} 
			current = current.next;
		}

	} 
	return null;
}

遍历节点

遍历节点其实在相关链表操作中都有运用，遍历节点需要一直移动到链表最后一个节点，即包含的指针指向null的节点，以打印节点为例:

this.toString = function() {
	var str = head.data;
	var current = head.next;

	while (current) {
		str += ','+ current.data;
		current = current.next;
	}

	return str;
}

完整实现代码

// 单项链表

function Node = function(data) {
	this.data = data;
	this.next = null;
}

function LinkList() {

	head = null;

	length = 0;

	
	// 在链表最后添加节点
	this.append = function(data) {
		var node = new Node(data);
		if (head == null) {
			head = node;
		} else {
			var current = head;
			var previous;
			while(current) {
				previous = current;
				current = current.next;
			}
			previous.next = node;
		}
		length++;
	}

	// 指定位置插入节点
	this.insert = function(pos, data) {
		var node = new Node(data);

		if (pos > -1 && pos < length) {
			if (pos == 0) {
				node.next = head;
				head = node;
			} else {
				var current = head;
				var previous;
				var index = 0;
				while(index++ < pos) {
					previous = current;
					current = current.next;
				}

				previous.next = node;
				node.next = current;
			}
			

			length++;
			return true;
		} 
		return false;
	}

	this.removeAt = function(pos) {
		if (pos > -1 && pos < length) {
			var current = head;
			var previous;
			var index = 0;
			while(index++ < pos) {
				previous = current;
				current = current.next;
			}

			previous.next = current.next;

			length--;
			return true;
		} 

		return false;
	}

	// 从链表尾部移除节点
	this.pop = function() {
		var current = head;
		var previous;

		while (current.next) {
			previous = current;
			current = current.next;
		}

		previous.next = null;

		length--;
	}

	// 搜索节点
	this.search = function(data) {
		if (data) {
			var current = head;
			var previous;

			while (current) {
				if (current.data == data) {
					return current;
				} 
				previous = current;
				current = current.next;
			}

		} 
		return null;
	}

	// 遍历节点
	this.toString = function() {
		var str = head.data;
		var current = head.next;

		while (current) {
			str += ','+ current.data;
			current = current.next;
		}

		return str;
	}

	// 获取链表长度
	this.getLength = function() {
		return length;
	}

}