JavaScript - 链表

创建链表

// util.js
export function defaultEquals(a, b) {
	return a === b
}
// linked-list-models.js
export class Node {
	constructor(element) {
		this.element = element;
		this.next = undefined;
	}
}
// 链表
import { defaultEquals } from 'util';
import { Node } from 'linked-list-models';
export default class LinkedList {
	constructor(equalsFn = defaultEquals) {
		this.count = 0;
		this.head = undefined;
		this.equalsFn = equalsFn;
		// 插入节点
		push(element) {
			const node = new Node(element);
			let current;
			if(this.head == null) {
				this.head = node;
			} else {
				current = this.head;
				while(current.next != null) {
					current = current.next;
				}
				current.next = node;
			}
			this.count += 1;
		}
		// 指定位置插入节点
		insert(element, index) {
			if(index >= 0 && index <= this.count) {
				const node = new Node(element);
				if(index === 0) {
					const current = this.head;
					node.next = current;
					this.head = node;
				} else {
					const previous = this.getElementAt(index - 1);
					const current = previous.next;
					node.next = current;
					previous.next = node;
				}
				this.count += 1;
				return true;
			}
			return false;
		}
		// 根据位置获取节点
		getElementAt(index) {
			if(index >= 0 && index <= this.count) {
				let node = this.head;
				for(let i = 0; i < index && node != null; i += 1) {
					node = node.next;
				}
				return node;
			}
			return undefined;
		}
		// 移除节点
		remove(element) {
			const index = this.indexOf(element);
			return this.removeAt(index);
		}
		// 获取节点位置
		indexOf(element) {
			let current = this.head;
			for(let i = 0; i < this.count && current != null; i += 1) {
				if(this.equalsFn(element, current.element)) {
					return i;
				}
				current = current.next;
			}
			return -1;
		}
		// 根据位置移除节点
		removeAt(index) {
			if(index > 0 && index < this.count) {
				let current = this.head;
				if(index === 0) {
					this.head = current.next;
				} else {
					const previous = this.getElementAt(index - 1);
					current = previous.next;
					previous.next = current.next;
				}
				this.count -= 1;
				return current.element;
			}
			return undefined;
		}
		isEmpty() {
			return this.size() === 0;
		}
		size() {
			return this.count;
		}
		getHead() {
			return this.head;
		}
		toString() {
			if(this.head == null) {
				return ''
			}
			let objString = `${this.head.element}`;
			let current = this.head.next;
			for(let i = 1; i < this.size() && current != null; i += 1) {
				objString += current.element;
				current = current.next
			}
			return objString;
		}
	}
}

双向链表

class DoublyNode extends Node {
  constructor(element, next, prev) {
    super(element, next, prev);
    this.prev = prev;
  }
}

class DoublyLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn);
    this.tail = undefined;
  }
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new DoublyNode(element);
      let current = this.head;
      if (index === 0) {
        if ((this.head = null)) {
          this.head = node;
          this.tail = node;
        } else {
          node.next = this.head;
          current.prev = node;
          this.head = node;
        }
      } else if (index === this.count) {
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        node.next = current;
        previous.next = node;
        node.prev = previous;
      }
      this.count += 1;
      return true;
    }
    return false;
  }
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = current.next;
        if (this.count === 1) {
          this.tail = undefined;
        } else {
          this.head.prev = undefined;
        }
      } else if (index === this.count - 1) {
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = undefined;
      } else {
        current = this.getElementAt(index);
        const previous = current.prev;
        previous.next = current.next;
        current.next.prev = previous;
      }
      this.count -= 1;
      return current.element;
    }
    return undefined;
  }
}

循环链表

class CircularLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals) {
    super(defaultEquals);
  }
  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      let current = this.head;
      if (index === 0) {
        if (this.head === null) {
          this.head = node;
          node.next = this.head;
        } else {
          node.next = current;
          current = this.getElementAt(this.size());
          this.head = node;
          current.next = this.head;
        }
      } else {
        const previous = this.getElementAt(index - 1);
        node.next = previous.next;
        previous.next = node;
      }
      this.count += 1;
      return true;
    }
    return false;
  }
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        if (this.size() === 1) {
          this.head = undefined;
        } else {
          const removed = this.head;
          current = this.getElementAt(this.size());
          this.head = this.head.next;
          current.next = this.head;
          current = removed;
        }
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count -= 1;
      return current.element;
    }
    return undefined;
  }
}