数据结构与算法 （链表实现篇）
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。链表的节点由数据和一个或多个指针域组成。链表在插入和删除操作上的算法复杂O(1),而数组的插入和删除的最大复杂度是O（n）。但是数组在查找比链表更优越。
单链表结构示意图
chain.png
链表结构分析
单链表由一个个数据域和指针域组成的节点组成的链式结构，单链表只有指向下一个节点的指针域；而双向链表由一个指向上一个节点和一个指向下一个节点的指针加数据域组成的链式结构。循环链表就是最后一个节点的指针不是指向null；而是指向head头部虚拟节点。如下图所示：
introduce.png
实现单链表结构的功能
- append(node)：append是往链表尾部添加节点操作，其中node是需要加入链表的元素，返回操作成功与否布尔值。
add.png
- remove(index)：delete移除第index个元素操作，返回移除的移除元素。
delete.png
size()：获取栈中的链表节点数量，返回一个数字。
isEmpty()：判断链表是否为空，返回一个布尔值。
find(head,currentIndex,index)：查找索引为index的节点，返回该节点。
find.png
ES6 单链表结构代码
class Node {
constructor(data, next) {
this.data = data;
this.next = next;
}
}
class LinkChain {
constructor() {
this.header = new Node(null, null);
this.size = 0;
}
find(header, currentIndex, index) {
if (currentIndex === index) {
return header;
}
return this.find(header.next, ++currentIndex, index);
}
append(data, index) {
const prevNode = this.find(this.header, 0, index);
prevNode.next = new Node(data, prevNode.next);
this.size++;
return true;
}
insert(node, index) {
return this.append(data, index);
}
remove(index) {
const prevNode = this.find(this.header, 0, index);
const node = prevNode.next;
prevNode.next = node.next;
node.next = null;
this.size--;
return node;
}
length() {
return thid.size;
}
isEmpty() {
return this.size === 0;
}
toString() {
console.log(JSON.stringify(this));
}
}
const chain = new LinkChain();
chain.append('kiwis', 0);
chain.append('kiwis1', 1);
chain.append('kiwis2', 2);
chain.toString();
ES5 单链表结构代码
通过ES5把功能函数可以绑定在对象的实例上，也可以把功能函数加在函数的原型链上
function Node(data,next){
this.data = data;
this.next = next;
}
function LinkChain(){
this.head = new Node(null,null);
this.length = 0;
}
LinkChain.prototype.append = function(data,index){
var prevNode = this.find(this.head,0,index);
prevNode.next = new Node(data,prevNode.next)
this.length++;
return true;
}
LinkChain.prototype.remove = function(index){
var prevNode = this.find(this.head,0,index);
var Node = prevNode.next;
prevNode.next = Node.next;
Node.next = null;
this.length--;
return Node;
}
LinkChain.prototype.size = function(){
return this.length;
}
LinkChain.prototype.isEmpty = function(){
return this.length === 0;
}
LinkChain.prototype.insert = function(node,index){
return this.append(node,index);
}
LinkChain.prototype.find = function(head,currentIndex,index){
if(currentIndex === index){
return head;
}
return this.find(head.next,++currentIndex,index);
}
双向链表
-
remove():移除节点操作，双向链表因为具有一个向上和一个向下的指针域，所以删除的时候需要解除两个指针的指向引用
delete.png -
insert(node,index):添加节点，双向链表因为具有一个向上和一个向下的指针域，所以添加的时候需要解除原来两个指针的指向引用，再进行添加指针指向操作。
insert
双向链表其他操作与单链表操作相类似，下面ES6实现双向链表的实现：
class Node{
constructor(data,next=null,prev=null){
this.data = data;
this.next = next;
this.prev = prev;
}
}
class LinkChain{
constructor(){
this.head = new Node(null,null,null);
this.tail = new Node(null,null,null);
this.length = 0;
}
find(head,currentIndex,index){
if(currentIndex === index){
return head;
}
return this.find(head.next,++currentIndex,index);
}
append(node,index){
const prevNode = this.find(this.head,0,index);
node.next = prevNode .next;
prevNode .next.prev = node;
prevNode.next = node;
node.prev = prevNode；
this.length++;
return true;
}
insert(node,index){
return this.append(node,index);
}
remove(index){
const prevNode = this.find(this.head,0,index);
const Node = prevNode.next;
prevNode.next = Node.next;
Node.next.prev = Node.prev;
Node.next = null;
Node.prev = null;
this.length--;
return Node;
}
size(){
return this.length;
}
isEmpty(){
return this.length === 0;
}
}
循环链表
introduce.png
循环链表的最后一个节点不再是指向null，而是指向虚拟的头部head指针，其他的操作相类似与单链表：
ES6实现循环链表代码：
append(node,index){
const prevNode = this.find(this.head,0,index);
const curtNode = prevNode.next;
if(!curtNode.next.data){
curtNode.next = node;
node.next = this.head;
}else{
node.next = curtNode.next;
curtNode.next = node;
}
this.length++;
return true;
}
remove(index){
const prevNode = this.find(this.head,0,index);
const curtNode = prevNode.next;
//如果只有一个虚拟head头部节点或删除的是最后一个节点
if(!curtNode.next.data){
prevNode.next = this.head;
}else{
prevNode.next = curtNode.next;
curtNode.next = null；
}
this.length --;
return true;
}
完成链表数据结构编码
