数据结构-链表（javascript版）

链表是常用的数据的一种，链表是节点的组合，节点包括指针和值，当列表为空值，头指针指向null，链表有单链表和双链表，下面我们针对单链表来展开，首先看下链表的“样子”

链表的代码实现

通过上面的图示，我们知道节点是由值和指针组成，我们通过代码来表示

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

接下来创建链表，链表是有一个head指针，size表示链表的节点个数

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
}

整个链表的结构已经创建好了，我们先了解节点是如何插入和删除的

节点插入图示

插入前

插入后

节点的删除

通过上面图示可以看出，链表节点的插入和删除操作就是操作指针的指向即可

接下来将会对链表新增以下方法，代码很简单，看注释即可

• add(value) 往链表新增节点
• insert(index, value) 指定位置插入节点
• removeByIndex(index) 指定位置删除节点
• indexOf(value) 查找目标值的节点下标
• removeByValue(value) 指定值删除节点
• pop() 弹出最后一个节点
• isEmpty() 判断节点是否为空
• print() 打印链表的值

add(value)

/**
  * 尾部新增节点
  * @param {*} value 
  */
add(value) {
  const node = new Node(value);
  let curr;
  if (this.head === null) {
    // 空链表
    this.head = node;
  } else {
    // 非空，获取到最后一个节点，更改指向
    curr = this.head;
    while (curr.next) {
      curr = curr.next;
    }
    curr.next = node;
  }
  this.size += 1;
}

insert(index, value)

/**
 * 指定位置插入节点
 * @param {*} index 
 * @param {*} value 
 * @returns 
 */
insert(index, value) {
  if (index < 0 || index > this.size - 1) {
    return false;
  } else {
    const node = new Node(value);
    let prev, curr = this.head;
    
    // 头部插入
    if (index === 0) {
      node.next = curr;
    } else {
      // 非头部插入，查找到节点，改变指针指向
      while (index > 0) {
        prev = curr;
        curr = curr.next;
        index -= 1;
      }
      prev.next = node;
      node.next = curr;
    }
    this.size += 1;
  }
}

removeByIndex(index)

/**
 * 通过下标移除节点
 * @param {*} index 
 * @returns 
 */
removeByIndex(index) {
  if (index < 0 || index > this.size - 1) {
    return;
  }
  let prev, curr = this.head;
  if (index === 0) {
    this.head = curr.next;
  } else {
    // 遍历获取指定下标的节点
    while (index > 0) {
      prev = curr;
      curr = curr.next;
      index -= 1;
    }
    prev.next = curr.next;
  }
  this.size -= 1;
  return curr.value;
}

indexOf(value)

/**
 * 查找目标值的节点下标
 * @param {*} value 
 * @returns 
 */
indexOf(value) {
  // 未找到返回-1
  let index = 0;
  let curr = this.head;
  while (curr) {
    if (curr.value === value) {
      // 找到了直接退出循环
      return index;
      break;
    }
    curr = curr.next;
    index += 1;
  }
  return -1;
}

removeByValue(value)

/**
 * 通过值移除节点
 * @param {*} value 
 * @returns 
 */
removeByValue(value) {
  const index = this.indexOf(value);
  return this.removeByIndex(index);
}

pop()

/**
 * 删除尾部节点
 */
pop() {
  let prev, curr = this.head;
  // 空链表，直接返回null
  if (this.size === 0) return null;
  if (!curr.next) {
    // 只有一个节点的情况
    this.head = null;
  } else {
    while (curr.next) {
      prev = curr;
      curr = curr.next;
    }
    prev.next = null;
  }
  this.size -= 1;
}

isEmpty()

/**
 * 判断是否为空
 */
isEmpty() {
  return this.size === 0;
}

print()

/**
 * 打印链表的值
 */
print() {
  const arr = [];
  let curr = this.head;
  while (curr) {
    arr.push(curr.value);
    curr = curr.next;
  }
  console.log(arr.join('->'))
}

结果测试

最后我们测试下结果

const linkList = new LinkedList();
linkList.add(1);
linkList.add(5);
linkList.add(8);
linkList.print(); // 1->5->8

linkList.insert(2, 4); 
linkList.print(); // 1->5->4->8

console.log(linkList.indexOf(5)); // 1

console.log('remove value is ' + linkList.removeByIndex(1)); // remove value is 5
linkList.print(); // 1->4->8

console.log('remove value is ' + linkList.removeByIndex(8)); // remove value is undefined
linkList.print(); // 1->4->8

linkList.removeByValue(4); 
linkList.print(); // 1->8

linkList.pop(); 
linkList.print(); // 1 

linkList.insert(0, 32); 
linkList.print(); // 32->1
linkList.insert(1, 44); 
linkList.print(); // 32->44->1

linkList.removeByValue(32);
linkList.print(); // 44->1

linkList.removeByValue(1);
linkList.print(); // 44

linkList.removeByValue(44);
linkList.print(); // 空

console.log(linkList.isEmpty()) // true