double-linked-circular-list

说明

双向循环链表

源码

用法

doubleLinkedCircularList.test.ts
import { DoubleLinkedCircularList } from "../../utility/algorithm/double-linked-circular-list";
import { ListNode } from "../../utility/algorithm/double-linked-circular-list/list-node";
// ? Double Linked Circular List
describe('DLCL', () => {
test('dlcl1.handleGetHead should return the `head` of linked-list', () => {
const dlcl1 = new DoubleLinkedCircularList<number>({
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
});
const expected = [2, 5, 8, 3, 7, 19, 23, 14, 41];
const head = dlcl1.handleGetHead();
const tail = dlcl1.handleGetTail();
// ? 正向遍历
let current: ListNode<number> | null = head;
let count: number = 0;
while (current && current !== tail) {
expect(current.value).toBe(expected[count]);
count++;
current = current.next;
}
if (current) {
expect(current.value).toBe(expected[count]);
// ? 重置
current = tail;
count = expected.length - 1;
}
// ? 反向遍历
while (current && current !== head) {
expect(current.value).toBe(expected[count]);
count--;
current = current.prev;
}
if (current) {
expect(current.value).toBe(expected[count]);
}
});
test('dlcl1.handleGetTail should return the `tail` of linked-list', () => {
const dlcl1 = new DoubleLinkedCircularList<number>({
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
});
const expected = [2, 5, 8, 3, 7, 19, 23, 14, 41];
const tail = dlcl1.handleGetTail();
const head = dlcl1.handleGetHead();
let current: ListNode<number> | null = tail;
let count: number = expected.length - 1;
// ? 反向遍历
while (current && current !== head) {
expect(current.value).toBe(expected[count]);
count--;
current = current.prev;
}
if (current) {
expect(current.value).toBe(expected[count]);
// ? 重置
count = 0;
current = head;
}
// ? 正向遍历
while (current && current !== tail) {
expect(current.value).toBe(expected[count]);
count++;
current = current.next;
}
if (current) {
expect(current.value).toBe(expected[count]);
}
});
test('dlcl1.handleGetLength should return the length of linked-list', () => {
const dlcl1 = new DoubleLinkedCircularList<number>({
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
});
const expected_1 = 9;
const expected_2 = 8;
const expected_3 = 10;
const result_1: number = dlcl1.handleGetLength();
expect(result_1).toBe(expected_1);
const result_2: number = dlcl1.handleRemove(41).handleGetLength();
expect(result_2).toBe(expected_2);
const result_3: number = dlcl1.handleAppend(41).handleAppend(100).handleGetLength();
expect(result_3).toBe(expected_3);
});
test('dlcl1.handleAppend should add new node to the tail of the linked-list', () => {
const dlcl1 = new DoubleLinkedCircularList<number>({
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
});
const expected_length_1 = 9;
const expected_value_1 = 41;
const expected_length_2 = 10;
const expected_value_2 = 100;
const expected_length_3 = 11;
const expected_value_3 = 200;
const result_length_1: number = dlcl1.handleGetLength();
const result_value_1: number = (dlcl1.handleGetTail() as ListNode<number>).value;
expect(result_length_1).toBe(expected_length_1);
expect(result_value_1).toBe(expected_value_1);
const result_length_2: number = dlcl1.handleAppend(100).handleGetLength();
const result_value_2: number = (dlcl1.handleGetTail() as ListNode<number>).value;
expect(result_length_2).toBe(expected_length_2);
expect(result_value_2).toBe(expected_value_2);
const result_length_3: number = dlcl1.handleAppend(200).handleGetLength();
const result_value_3: number = (dlcl1.handleGetTail() as ListNode<number>).value;
expect(result_length_3).toBe(expected_length_3);
expect(result_value_3).toBe(expected_value_3);
});
test('dlcl1.handlePrepend should add new node to the head of the linked-list', () => {
const dlcl1 = new DoubleLinkedCircularList<number>({
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
});
const expected_length_1 = 9;
const expected_value_1 = 2;
const expected_length_2 = 10;
const expected_value_2 = 100;
const expected_length_3 = 11;
const expected_value_3 = 200;
const result_length_1: number = dlcl1.handleGetLength();
const result_value_1: number = (dlcl1.handleGetHead() as ListNode<number>).value;
expect(result_length_1).toBe(expected_length_1);
expect(result_value_1).toBe(expected_value_1);
const result_length_2: number = dlcl1.handlePrepend(100).handleGetLength();
const result_value_2: number = (dlcl1.handleGetHead() as ListNode<number>).value;
expect(result_length_2).toBe(expected_length_2);
expect(result_value_2).toBe(expected_value_2);
const result_length_3: number = dlcl1.handlePrepend(200).handleGetLength();
const result_value_3: number = (dlcl1.handleGetHead() as ListNode<number>).value;
expect(result_length_3).toBe(expected_length_3);
expect(result_value_3).toBe(expected_value_3);
});
test('dlcl1.handleInsertBefore should add new list-node to the front of the target node', () => {
const dlcl1 = new DoubleLinkedCircularList<number>({
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
});
const expected_length_1 = 10;
const expected_value_1 = 100;
const expected_length_2 = 11;
const expected_value_2 = 200;
// ? 头节点
const result_length_1: number = dlcl1.handleInsertBefore(2, 100).handleGetLength();
const result_value_1: number = (dlcl1.handleGetHead() as ListNode<number>).value;
expect(result_length_1).toBe(expected_length_1);
expect(result_value_1).toBe(expected_value_1);
// ? 其它部位
const result_length_2: number = dlcl1.handleInsertBefore(2, 200).handleGetLength();
const result_value_2: number = ((dlcl1.handleGetHead() as ListNode<number>).next as ListNode<number>).value;
expect(result_length_2).toBe(expected_length_2);
expect(result_value_2).toBe(expected_value_2);
});
test("dlcl1.handleInsertAfter should add new list-node to the back of the target node", () => {
const dlcl1 = new DoubleLinkedCircularList<number>({
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
});
const expected_length_1 = 10;
const expected_value_1 = 100;
const expected_length_2 = 11;
const expected_value_2 = 200;
// ? 尾部节点
const result_length_1: number = dlcl1.handleInsertAfter(41, 100).handleGetLength();
const result_value_1: number = (dlcl1.handleGetTail() as ListNode<number>).value;
expect(result_length_1).toBe(expected_length_1);
expect(result_value_1).toBe(expected_value_1);
// ? 其它部位
const result_length_2: number = dlcl1.handleInsertAfter(41, 200).handleGetLength();
const result_value_2: number = ((dlcl1.handleGetTail() as ListNode<number>).prev as ListNode<number>).value;
expect(result_length_2).toBe(expected_length_2);
expect(result_value_2).toBe(expected_value_2);
});
test('dlcl1.handleRemove should remove special node from the linked-list', () => {
const dlcl1 = new DoubleLinkedCircularList<number>({
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
});
const received_value = 7;
const expected_length = 8;
const expected_value = false;
const result_length: number = dlcl1.handleRemove(7).handleGetLength();
expect(result_length).toBe(expected_length);
let sign: boolean = false;
dlcl1.handleTraversalWithForward((node) => {
if (node.value === received_value) {
sign = true;
}
});
expect(sign).toBe(expected_value);
});
test('dlcl1.handleTraversalWithForward should traversal the linked-list forwardly', () => {
const dlcl1 = new DoubleLinkedCircularList<number>({
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
});
const expected = [2, 5, 8, 3, 7, 19, 23, 14, 41];
let sign = false;
let count = 0;
dlcl1.handleTraversalWithForward((node) => {
node.value !== expected[count] && (sign = true);
count++;
});
expect(sign).toBeFalsy();
});
test('dlcl1.handleTraversalWithBackward should traversal the linked-list backwardly', () => {
const dlcl1 = new DoubleLinkedCircularList<number>({
nodes: [2, 5, 8, 3, 7, 19, 23, 14, 41],
});
const expected = [41, 14, 23, 19, 7, 3, 8, 5, 2];
let sign = false;
let count = 0;
dlcl1.handleTraversalWithBackward((node) => {
node.value !== expected[count] && (sign = true);
count++;
});
expect(sign).toBeFalsy();
});
});

API

Name
Type
Description
handleGetHead
() => ListNode | null
获取头节点
handleGetTail
() => ListNode | null
获取尾节点
handleAppend
(value: V) => DoubleLinkedCircularList<V>
尾部追加节点
handlePrepend
(value: V) => DoubleLinkedCircularList<V>
首部追加节点
handleInsertBefore
(target: V, value: V) => DoubleLinkedCircularList<V>
将目标节点插入至源节点前
handleInsertAfter
(target: V, value: V) => DoubleLinkedCircularList<V>
将目标节点插入至源节点后
handleTraversalWithForward
(callback: (node: ListNode<V>) => void) => void
正向遍历双向循环链表
handleTraversalWithBackward
(callback: (node: ListNode<V>) => void) => void
反向遍历双向循环链表
handleGetLength
() => number
获取链表长度
handleRemove
(value: V) => DoubleLinkedCircularList
移除链表指定节点
复制链接