链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。
链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。
在数组中，可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，则需要从起点开始迭代链表直到找到所需的元素。
class Node {
constructor(element, next) {
this.element = element
this.next = next
}
}
class LinkedList {
constructor(equalsFn = defaultEquals) {
this.equalsFn = equalsFn
this.count = 0
this.head = undefined
}
push(element) {
const node = new Node(element)
let current
if (this.head == null) {
// catches null && undefined
this.head = node
} else {
current = this.head
while (current.next != null) {
current = current.next
}
current.next = node
}
this.count++
}
getElementAt(index) {
if (index >= 0 && index <= this.count) {
let node = this.head
for (let i = 0; i < index && node != null; i++) {
node = node.next
}
return node
}
return undefined
}
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)
node.next = previous.next
previous.next = node
}
this.count++
return true
}
return false
}
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--
return current.element
}
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.size() && current != null; i++) {
if (this.equalsFn(element, current.element)) {
return i
}
current = current.next
}
return -1
}
isEmpty() {
return this.size() === 0
}
size() {
return this.count
}
getHead() {
return this.head
}
clear() {
this.head = undefined
this.count = 0
}
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++) {
objString = `${objString},${current.element}`
current = current.next
}
return objString
}
}链接是双向的：一个链向下一个元素，另一个链向前一个元素。
class Node {
constructor(element, next) {
this.element = element
this.next = next
}
}
class DoublyNode extends Node {
constructor(element, next, prev) {
super(element, next)
this.prev = prev
}
}
class DoublyLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn)
this.tail = undefined
}
push(element) {
const node = new DoublyNode(element)
if (this.head == null) {
this.head = node
this.tail = node // NEW
} else {
// attach to the tail node // NEW
this.tail.next = node
node.prev = this.tail
this.tail = node
}
this.count++
}
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) {
// NEW
this.head = node
this.tail = node // NEW
} else {
node.next = this.head
this.head.prev = node // NEW
this.head = node
}
} else if (index === this.count) {
// last item NEW
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
current.prev = node // NEW
node.prev = previous // NEW
}
this.count++
return true
}
return false
}
removeAt(index) {
if (index >= 0 && index < this.count) {
let current = this.head
if (index === 0) {
this.head = this.head.next
// if there is only one item, then we update tail as well //NEW
if (this.count === 1) {
// {2}
this.tail = undefined
} else {
this.head.prev = undefined
}
} else if (index === this.count - 1) {
// last item //NEW
current = this.tail
this.tail = current.prev
this.tail.next = undefined
} else {
current = this.getElementAt(index)
const previous = current.prev
// link previous with current's next - skip it to remove
previous.next = current.next
current.next.prev = previous // NEW
}
this.count--
return current.element
}
return undefined
}
indexOf(element) {
let current = this.head
let index = 0
while (current != null) {
if (this.equalsFn(element, current.element)) {
return index
}
index++
current = current.next
}
return -1
}
getHead() {
return this.head
}
getTail() {
return this.tail
}
clear() {
super.clear()
this.tail = undefined
}
toString() {
if (this.head == null) {
return ""
}
let objString = `${this.head.element}`
let current = this.head.next
while (current != null) {
objString = `${objString},${current.element}`
current = current.next
}
return objString
}
inverseToString() {
if (this.tail == null) {
return ""
}
let objString = `${this.tail.element}`
let previous = this.tail.prev
while (previous != null) {
objString = `${objString},${previous.element}`
previous = previous.prev
}
return objString
}
}循环链表可以像链表一样只有单项引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别是最后一个元素指向下一个元素的指针不是引用 undefined，而是指向第一个元素。
class Node {
constructor(element, next) {
this.element = element
this.next = next
}
}
class CircularLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals) {
super(equalsFn)
}
push(element) {
const node = new Node(element)
let current
if (this.head == null) {
this.head = node
} else {
current = this.getElementAt(this.size() - 1)
current.next = node
}
// set node.next to head - to have circular list
node.next = this.head
this.count++
}
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) {
// if no node in list
this.head = node
node.next = this.head
} else {
node.next = current
current = this.getElementAt(this.size())
// update last element
this.head = node
current.next = this.head
}
} else {
const previous = this.getElementAt(index - 1)
node.next = previous.next
previous.next = node
}
this.count++
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() - 1)
this.head = this.head.next
current.next = this.head
current = removed
}
} else {
// no need to update last element for circular list
const previous = this.getElementAt(index - 1)
current = previous.next
previous.next = current.next
}
this.count--
return current.element
}
return undefined
}
}有序链表是指保持元素有序的链表结构。
const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1,
EQUALS: 0
}
function defaultCompare(a, b) {
if (a === b) {
return Compare.EQUALS
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN
}
function defaultEquals(a, b) {
return a === b
}
class SortedLinkedList extends LinkedList {
constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
super(equalsFn)
this.equalsFn = equalsFn
this.compareFn = compareFn
}
push(element) {
if (this.isEmpty()) {
super.push(element)
} else {
const index = this.getIndexNextSortedElement(element)
super.insert(element, index)
}
}
insert(element, index = 0) {
if (this.isEmpty()) {
return super.insert(element, index === 0 ? index : 0)
}
const pos = this.getIndexNextSortedElement(element)
return super.insert(element, pos)
}
getIndexNextSortedElement(element) {
let current = this.head
let i = 0
for (; i < this.size() && current; i++) {
const comp = this.compareFn(element, current.element)
if (comp === Compare.LESS_THAN) {
return i
}
current = current.next
}
return i
}
}