链表

一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据

单项链表

单项链表的基本结构

class Node {
  constructor(public element = element, public next = null) {}
}
class LinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
  }
  public append(element: any) {}
  public insert(position: number, element: Node) {}
  public removeAt(position: number){}
  public remove(element: Node){}
  public indexOf(element: Node){}
  public isEmpty(): boolean{}
  public size(): number{}
  public getHead(): Node{}
  public toString(): string {}
  public print() {}
}

向链表尾部追加元素

向链表对象尾部添加一个元素时,可能有两种场景: 列表空时,添加的是第一个元素,列表不为空时,向其追加元素

// 省略部分代码
public append(element: Node) {
  const node = new Node(element);
  let current;
  // 列表为空时添加为第一个元素
  if (this.head === null) {
    head = node;
  } else {
    current = this.head;
    while(current.next) {
      current = current.next;
    }
    current.next = node;
  }
  this.length += 1;
}
// 省略部分代码

从链表中移除元素

移除元素也分两种场景: 移除第一个元素或移除第一个以外的任一元素

// 省略部分代码
/**
 * 移除指定位置的元素
 * */
public removeAt(position: number) {
  if (position > -1 && position < length) {
    let current = this.head;
    let previous;
    let index = 0;

    // 移除第一项
    if (position === 0) {
      this.head = current.next;
    } else {
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
    }
    this.length -= 1;
    return current.element;
  } else {
    return null;
  }
}
// 省略部分代码

移除列表最后一项或中间某一项时, 需要依靠一个细节来迭代列表,直到到达目标位置,使用一个内部递增的index变量, current变量为所

循环列表的当前元素进行引用,以及一个对当前元素的前一个元素引用的变量previous

从列表中删除当前元素,要做的就是将previous.next和current.next连接起来

在任意位置插入一个元素

insert方法用于在任意位置插入一个元素

public insert(position: number, element: any): boolean {
  if (position >= 0 && position <= this.length) {
    const node = new Node(element);
    let current = this.head;
    let previous;
    let index = 0;

    // 当position为0 则在第一个位置添加新元素
    if (position === 0) {
      node.next = current;
      head = node;
    } else {
      while(index++ < position) {
        previous = current;
        current = current.next;
      }
      node.next = current;
      previous.next = node;
    }
    this.length += 1;
    return true;
  } else {
    return false;
  }
}

当插入位置为0时,先把新插入node的next设为当前head,再把head修改为node,就成功把新元素插入到了列表头部

当插入位置在中间或尾部时,循环遍历列表,找到目标位置,在previous和current中间添加新元素,将新元素的next设为current,previous的next设为新元素,这样就成功在列表中间插入了新元素

其他方法

toString

toString方法需要将LinkedList对象转换成一个字符串

public toString() {
  let current = this.head;
  let string = '';

  while(current) {
    string += current.element + (current.next ? 'n' : '');
    current = current.next;
  }
  return string;
}

indexOf

indexOf方法接受一个元素的值,如果在列表中找到它,就返回元素的位置,否则返回-1

public indexOf(element: any) {
  let current = this.head;
  let index = -1;
  while(current) {
    if (element === current.element) {
      return index;
    }
    index += 1;
    current = current.next;
  }
  return -1;
}

remove

remove方法可以依赖indexOf方法先找到要移除元素的index,然后调用this.removeAt将index传进去从而删除元素

public remove(element: any) {
  const index = this.indexOf(element);
  return this.removeAt(index);
}

isEmpty && size && getHead

public isEmpty() {
  return this.length === 0;
}

public size() {
  return this.length;
}

public getHead() {
  return this.head;
}

双向链表

双向链表与单项链表的区别是,双向链表有两个分别指向上一个元素以及下一个元素的链接

因此,双向链表除了head属性外,还有一个表示尾部元素的tail属性

class DoublyLinkedList {
  constructor {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }
}

双向链表还提供了两种迭代列表的方法: 从头到尾以及从尾到头.我们也可以访问一个特定节点的下一个或上一个元素

任意位置插入新元素

双向链表插入操作和单项链表相似,唯一的区别是单项链表只需要维护一个next指针,而双向链表需要同时维护next和prev指针

public insert(position: number, element: any): boolean {
  if (position >= 0 && position <= this.length) {
    const node = new Node(element);
    let current = this.head;
    let previous;
    let index = 0;

    if (position === 0) {
      if (!this.head) {
        this.head = node;
        this.tail = node;
      } else {
        node.next = current;
        current.prev = node;
        this.head = node;
      }
    } else if (positon === length) {
      current = this.tail;
      current.next = node;
      node.prev = current;
      this.tail = node;
    } else {
      whild (index++ < position) {
        previous = current;
        current = current.next;
      }
      node.next = current;
      previous.next = node;
      current.prev = node;
      node.prev = previous;
    }
    this.length += 1;
    return true;
  } else {
    return false;
  }
}

头部插入,如果头部为null,则把head和tail都设为新元素. 如果头部已经存在,则把头部元素赋值给current,新元素的next设为current,current的prev设为新元素,同时把尾部指针设为新元素
尾部插入, 将尾部元素赋值给current, current的next指向新元素,新元素的prev再指向current,最后把尾部指针指向新元素
中间插入, 循环遍历列表,将当前元素赋值给previous,当前元素则改为current的next,再把新元素的next指向当前元素,previous的next指向新元素,最后把当前元素的prev指向新元素,新元素的prev指向previous

从任意位置移除元素

public removeAt(position: number) {
  if (position > -1 && position < this.length) {
    let current = this.head;
    let previous;
    let index = 0;

    if (position === 0) {
      this.head = current.next;
      if (this.length === 1) {
        this.tail = null;
      } else {
        this.head.prev = null;
      }
    } else if (position === this.length - 1) {
      current = this.tail;
      this.tail = current.prev;
      this.tail.next = null;
    } else {
      while (index++ < position) {
        previous = current;
        current = current.next;
      }

      previous.next = current.next;
      current.next.prev = previous;
    }
    this.length -= 1;
    return current.element;
  } else {
    return null;
  }
}

同样需要处理三种场景

头部移除, 将当前头部赋值给current, 之后将头部设为current的next, 如果列表只有一项,则把tail设为null,否则将头部的prev设为null
尾部移除, 将当前尾部赋值给current, 之后将尾部设为current的prev, 尾部的next设为null
中间移除, 循环遍历列表, 将当前项赋值给previous, current修改为current的next, 最后将previous的next设为current的next, current的next的prev设为previous, 完成中间指定位置移除

循环链表

循环链表可以像链表一样只有单向引用,也可以像双向链表一样有双向引用,循环链表和链表之间唯一的区别是,最后一个元素的next指针并不指向null,而是头部元素

Aaaaash / blog

数据结构之-链表 #8

链表