上海招聘信息网官网汉川seo推广

当前位置： 首页 > news >正文

上海招聘信息网官网,汉川seo推广,北京seo学校,抛丸机网站怎么做目录 比较操作结构封装单向链表实现面试题 循环链表实现 双向链表实现 链表#xff08;Linked List#xff09;是一种线性数据结构#xff0c;由一组节点#xff08;Node#xff09;组成#xff0c;每个节点包含两个部分#xff1a;数据域#xff08;存储数据#xff… 目录 比较操作结构封装单向链表实现面试题 循环链表实现 双向链表实现 链表Linked List是一种线性数据结构由一组节点Node组成每个节点包含两个部分数据域存储数据和指针域指向下一个节点的地址。与数组不同链表中的元素在内存中不是连续存储的使用指针进行连接 链表类似于火车有一个火车头火车头会连接一个节点节点上有乘客(类似于数据)并且这个节点会连接下一个节点以此类推 实现栈和队列链表结构非常适合实现这些数据结构。 LRU缓存双向链表和哈希表结合实现。 操作系统进程管理使用链表管理进程调度队列。 图和树结构使用链表作为底层存储
比较 链表和数组一样可以用于存储一系列的元素但是链表和数组的实现机制完全不同 数组 数组的创建通常需要申请一段连续的内存空间(一整块的内存)并且大小是固定的(大多数编程语言数组都是固定的) 当前数组不能满足容量需求时需要扩容。 (一般情况下是申请一个更大的数组比如2倍然后将原数组中的元素复制过去) 在数组开头或中间位置插入数据的成本很高需要进行大量元素的位移 链表 链表中的元素在内存中不必是连续的空间可以充分利用计算机的内存实现灵活的内存动态管理 链表不必在创建时就确定大小并且大小可以无限的延伸下去 链表在插入和删除数据时时间复杂度可以达到O(1)相对数组效率高很多 链表访问任何一个位置的元素时都需要从头开始访问。(无法跳过第一个元素访问任何一个元素) 链表无法通过下标直接访问元素需要从头一个个访问直到找到对应的元素 时间复杂度对比 在实际开发中选择使用数组还是链表 需要根据具体应用场景来决定 如果数据量不大且需要频繁随机 访问元素使用数组可能会更好 如果数据量大或者需要频繁插入 和删除元素使用链表可能会更好
操作 append(element)向链表尾部添加一个新的项 travers()为了可以方便的看到链表上的每一个元素我们实现一个遍历链表每一个元素的方法 insert(positionelement)向链表的特定位置插入一个新的项 get(position)获取对应位置的元素 indexOf(element)返回元素在链表中的索引。如果链表中没有该元素则返-1 update(positionelement)修改某个位置的元素 removeAt(position)从链表的特定位置移除一项 remove(element)从链表中移除一项 peek()头的值 isEmpty()如果链表中不包含任何元素返回true如果链表长度大于0则返回false size()链表的长度
结构封装 封装一个Node类用于封装每一个节点上的信息包括值和指向下一个节点的引用它是一个泛型类 封装一个LinkedList类用于表示我们的链表结构和操作 链表中我们保存三个属性一个是链表的长度一个是链表中第一个节点这里也加最后一个节点方便实现循环和双向链表
class NodeT {value: T;next: NodeT;constructor(value: T) {this.value value;} }export interface ILinkedListT {append(value: T): void;traverse(): void;insert(value: T, position: number): boolean;removeAt(position: number): T | null;get(position: number): T | null;update(value: T, position: number): boolean;indexOf(value: T): number;remove(value: T): T | null;isEmpty(): boolean;size(): number }class LinkedListT implements ILinkedListT {head: NodeT | null null;tail: NodeT | null null;length: number 0;append(value: T): void {throw new Error(Method not implemented.);}traverse(): void {throw new Error(Method not implemented.);}insert(value: T, position: number): boolean {throw new Error(Method not implemented.);}removeAt(position: number): T | null {throw new Error(Method not implemented.);}get(position: number): T | null {throw new Error(Method not implemented.);}update(value: T, position: number): boolean {throw new Error(Method not implemented.);}indexOf(value: T): number {throw new Error(Method not implemented.);}remove(value: T): T | null {throw new Error(Method not implemented.);}peek(value: T): T | undefined {throw new Error(Method not implemented.);}isEmpty(): boolean {throw new Error(Method not implemented.);}size(): number {throw new Error(Method not implemented.);} }const linked new LinkedListstring(); console.log(linked.head); // null单向链表 实现 在下面实现各种方法时我们会定义变量 previous 来保存前一个节点和 current 保存当前节点 各种方法实现都是通过操作变量来达到操作链表 这是因为变量实际上是链表中节点的引用而不是节点的副本 链表的节点是对象变量实际上指向的是链表中某个节点的内存地址引用 因此当我们修改变量时也会影响链表中的节点这种机制使得我们能够轻松操作链表中的节点 部分方法图解如下 append(element) 向链表表尾部追加数据 链表为空直接赋值为head 链表不为空需要向其他节点后面追加节点 insert(positionelement) 添加到第一个位置表示新添加的节点是头需要将原来的头节点作为新节点的nexthead指向新节点 添加到其他位置需要先找到这个节点位置通过循环向下找并在这个过程中保存上一个节点和下一个节点找到正确的位置后将新节点的next指向下一个节点将上一个节点的 next 指向新的节点步骤颠倒后续链表之间的连接就会断掉 removeAt(position)从链表的特定位置移除一项 移除第一项时直接让head指向第二项信息第一项信息没有引用指向后面会被回收掉 移除其他项的信息时通过循环找到正确的位置将上一项的next指向current 项的next 完整代码如下 抽取共同方法 export class NodeT {value: T;next: NodeT | null null;constructor(value: T) {this.value value;} }export interface ILinkedListT {append(value: T): void;traverse(): void;insert(value: T, position: number): boolean;removeAt(position: number): T | null;get(positon: number): T | null;update(value: T, position: number): boolean;indexOf(value: T): number;remove(value: T): T | null;peek(value: T): T | undefined;isEmpty(): boolean;size(): number; }export class LinkedListT implements ILinkedListT {// 使用protected也是为了让其子类继承时使用protected head: NodeT | null null;protected tail: NodeT | null null;protected length: number 0;protected getNode(position: number): {previous: NodeT | null;current: NodeT | null;} {let index 0;let previous: NodeT | null null;let current this.head;while (index position current) {previous current;current current.next;}return { current, previous };}private isTail(node: NodeT) {return this.tail node;}/* 向链表表尾部追加数据 /append(value: T): void {const newNode new Node(value);// 链表为空直接赋值为headif (!this.head) {this.head newNode;} else {// 链表不为空循环找到尾部节点让其next指向新节点完成追加// let current this.head;// while (current.next) {// current current.next;// }// current.next newNode;this.tail!.next newNode;}this.tail newNode;this.length;}/ 链表的遍历方法 /traverse(): void {let values: T[] [];let current this.head;while (current) {values.push(current.value);current this.isTail(current) ? null : current.next; // 考虑循环链表的情况}if (this.head this.tail!.next this.head) {// 循环链表时values.push(this.head.value);}console.log(this.length, values.join( - ));}/ 向链表的特定位置插入一个新的项 /insert(value: T, position: number): boolean {// 1.越界的判断if (position 0 position this.length) return false;// 2.根据value创建新的节点const newNode new Node(value);let { previous, current } this.getNode(position);// 头部插入if (position 0) {newNode.next this.head;this.head newNode;} else {// 中尾部插入newNode.next current;previous!.next newNode;if (position this.length) {// 尾部插入tail为新节点this.tail newNode;}}this.length;return true;}removeAt(position: number): T | null {// 1.越界的判断if (position 0 || position this.length) return null;let { current, previous } this.getNode(position);if (position 0) {this.head current?.next ?? null;if (this.length 1) {this.tail null;}} else {previous!.next current?.next ?? null;if (current this.tail) {// 尾部删除tail为前一个节点this.tail previous;}}this.length–;return current?.value ?? null;}// 获取方法get(position: number): T | null {// 越界问题if (position 0 || position this.length) return null;let { current } this.getNode(position);return current?.value ?? null;}// 更新方法update(value: T, position: number): boolean {if (position 0 || position this.length) return false;// 获取对应位置的节点, 直接更新即可let { current } this.getNode(position);current!.value value;return true;}// 根据值, 获取对应位置的索引indexOf(value: T): number {let index 0;let current this.head;while (current) {if (current.value value) return index;current this.isTail(current) ? null : current.next; // 考虑循环链表的情况index;}return -1;}// 删除方法: 根据value删除节点remove(value: T): T | null {const index this.indexOf(value);return this.removeAt(index);}peek(): T | undefined {return this.head?.value;}// 判读单链表是否为空isEmpty(): boolean {return this.length 0;}size(): number {return this.length;} }const linked new LinkedListstring(); linked.append(aaa); linked.append(bbb); linked.append(ccc); linked.traverse(); // 3 aaa - bbb - ccclinked.insert(zzz, 0); linked.insert(ddd, 2); linked.insert(eee, 5); linked.traverse(); // 6 zzz - aaa - ddd - bbb - ccc - eeeconsole.log(linked.removeAt(0)); // zzz console.log(linked.removeAt(1)); // ddd console.log(linked.removeAt(3)); // eee linked.traverse(); // 3 aaa - bbb - cccconsole.log(linked.get(0)); // aaa console.log(linked.get(1)); // bbb console.log(linked.get(2)); // ccc console.log(linked.get(3)); // nullconsole.log(linked.update(aa, 0)); // true console.log(linked.update(cc, 2)); // true console.log(linked.update(dd, 3)); // false linked.traverse(); // 3 aa - bbb - ccconsole.log(linked.indexOf(aa)); // 0 console.log(linked.indexOf(ccc)); // -1linked.remove(bbb); linked.traverse(); // 2 aa - ccconsole.log(linked.isEmpty()); // false面试题 设计链表 https://leetcode.cn/problems/design-linked-list/description/ 上面代码已经完成 删除链表中的节点 https://leetcode.cn/problems/delete-node-in-a-linked-list/description/ class ListNode {val: number;next: ListNode | null;constructor(val?: number, next?: ListNode | null) {this.val val undefined ? 0 : val;this.next next undefined ? null : next;} }function deleteNode(node: ListNode | null): void {node!.val node!.next!.valnode!.next node!.next!.next }反转链表 https://leetcode.cn/problems/reverse-linked-list/description/ 非递归实现 class Node {val: number;next: ListNode | null;constructor(val?: number, next?: ListNode | null) {this.val val undefined ? 0 : val;this.next next undefined ? null : next;} } function reverseList(head: Node | null): Node | null {// 1.判断节点为null, 或者只要一个节点, 那么直接返回即可if (head null || head.next null) return head;let previous: Node | null null;while (head) {const current: Node | null head.next;head.next previous;previous head;head current;}return previous; }递归实现 function reverseListT(head: Node | null): Node | null {// 如果使用的是递归, 那么递归必须有结束条件if (head null || head.next null) return head;const newHead reverseList(head?.next ?? null);head.next.next head;head.next null;return newHead; } let n new Node(1); n.next new Node(2); n.next.next new Node(3); n.next.next.next new Node(4); n.next.next.next.next new Node(5);let current reverseList(n); while (current) {console.log(current.value); // 5 4 3 2 1current current.next; }循环链表 循环链表Circular Linked List是一种特殊的链表结构其中链表的最后一个节点指向链表的第一个节点从而形成一个闭环。它的主要特性是任何一个节点都可以通过不断访问 next 指针回到起点节点因此在循环链表中没有空指针这种终止条件
实现 方式一从零去实现一个新的链表包括其中所有的属性和方法 方式二继承自之前封装的LinkedList只实现差异化的部分我们使用这个方式 实现代码如下实现append、实现insert、实现removeAt、indexOf和traverse在写单向链表时判断了循环的情况不需要再重构 import { LinkedList } from ./单向链表实现.ts;class CircularLinkedListT extends LinkedListT {append(value: T): void {super.append(value);this.tail!.next this.head;}insert(value: T, position: number): boolean {const isSuccess super.insert(value, position);if (isSuccess (position this.length - 1 || position 0)) {// 如果插入成功 尾部插入 || 头部插入都需要更新tail.nextthis.tail!.next this.head;}return isSuccess;}removeAt(position: number): T | null {const value super.removeAt(position);if (value this.tail (position this.length - 1 || position 0)) {// 如果删除成功 tail null 尾部删除 || 头部删除都需要更新tail.nextthis.tail!.next this.head;}return value;} }const linked new CircularLinkedListstring(); linked.append(aaa); linked.append(bbb); linked.append(ccc); linked.traverse(); // 3 aaa - bbb - ccc - aaalinked.insert(zzz, 0); linked.insert(ddd, 2); linked.insert(eee, 5); linked.traverse(); // zzz - aaa - ddd - bbb - ccc - eee - zzzconsole.log(linked.removeAt(0)); // zzz console.log(linked.removeAt(1)); // ddd console.log(linked.removeAt(3)); // eee linked.traverse(); // 3 aaa - bbb - ccc - aaaconsole.log(linked.get(0)); // aaa console.log(linked.get(1)); // bbb console.log(linked.get(2)); // ccc console.log(linked.get(3)); // nullconsole.log(linked.update(aa, 0)); // true console.log(linked.update(cc, 2)); // true console.log(linked.update(dd, 3)); // false linked.traverse(); // 3 aa - bbb - cc - aaconsole.log(linked.indexOf(aa)); // 0 console.log(linked.indexOf(ccc)); // -1linked.remove(bbb); linked.traverse(); // 2 aa - cc - aaconsole.log(linked.isEmpty()); // false双向链表 双向链表Doubly Linked List是一种数据结构类似于单向链表但每个节点包含两个指针一个指向下一个节点一个指向前一个节点
优点 可以从头到尾、也可以从尾到头进行遍历灵活性更高 删除和插入操作时不需要像单向链表那样只能从头遍历找到前一个节点 缺点 每个节点需要额外的指针prev会占用更多的存储空间 每次在插入或删除某个节点时需要处理四个引用实现起来要困难一些
实现 封装双向链表节点需要进一步添加一个prev属性用于指向前一个节点 实现代码如下因为差距较大重新实现append、insert、removeAt新增加prepend在头部添加元素、postTraverse从尾部遍历所有节点 import { LinkedList, Node } from ./单向实现;class DoublyNodeT extends NodeT {next: DoublyNodeT | null null;prev: DoublyNodeT | null null; }class DoublyLinkedListT extends LinkedListT {protected head: DoublyNodeT | null null;protected tail: DoublyNodeT | null null;// 尾部追加元素append(value: T): void {const newNode new DoublyNode(value);if (!this.head) {this.head newNode;} else {this.tail!.next newNode;// 不能将一个父类的对象, 赋值给一个子类的类型// 可以将一个子类的对象, 赋值给一个父类的类型(多态)newNode.prev this.tail;}this.tail newNode;this.length;}// 插入元素insert(value: T, position: number): boolean {if (position 0 position this.length) return false;if (position 0) {this.prepend(value);} else if (position this.length) {this.append(value);} else {const newNode new DoublyNode(value);/ 使用 as 断言它是 DoublyNodeT 类型那么在后续代码中TypeScript 会允许你访问 DoublyNodeT 类型中的属性例如 prev即使这个属性在 NodeT 类型中并未定义*/const current this.getNode(position).current as DoublyNodeT;newNode.next current;newNode.prev current.prev;current.prev!.next newNode;current.prev newNode;this.length;}return true;}// 删除元素removeAt(position: number): T | null {if (position 0 || position this.length) return null;let current this.head;if (position 0) {if (this.length 1) {this.head null;this.tail null;} else {this.head this.head!.next;this.head!.prev null;}} else if (position this.length - 1) {current this.tail;this.tail this.tail!.prev;this.tail!.next null;} else {current this.getNode(position).current as DoublyNodeTcurrent!.next!.prev current!.prev;current!.prev!.next current!.next;}this.length–;return current?.value ?? null;}// 在头部添加元素prepend(value: T): boolean {const newNode new DoublyNode(value);newNode.next this.head;if (this.head) {this.head.prev newNode;} else {this.tail newNode;}this.head newNode;this.length;return true;}// 从尾部开始遍历所有节点postTraverse() {let values: T[] [];let current this.tail;while (current) {values.push(current.value);current current.prev;}console.log(this.length, values.join( - ));} }const linked new DoublyLinkedListstring();linked.prepend(aaa); linked.append(bbb); linked.append(ccc); linked.traverse(); // 3 aaa - bbb - ccc linked.postTraverse(); // 3 ccc - bbb - aaalinked.insert(zzz, 0); linked.insert(ddd, 2); linked.insert(eee, 5); linked.traverse(); // 6 zzz - aaa - ddd - bbb - ccc - eeeconsole.log(linked.removeAt(0)); // zzz console.log(linked.removeAt(1)); // ddd console.log(linked.removeAt(3)); // eee linked.traverse(); // 3 aaa - bbb - cccconsole.log(linked.get(0)); // aaa console.log(linked.get(1)); // bbb console.log(linked.get(2)); // ccc console.log(linked.get(3)); // nullconsole.log(linked.update(aa, 0)); // true console.log(linked.update(cc, 2)); // true console.log(linked.update(dd, 3)); // false linked.traverse(); // 3 aa - bbb - ccconsole.log(linked.indexOf(aa)); // 0 console.log(linked.indexOf(ccc)); // -1linked.remove(bbb); linked.traverse(); // 2 aa - ccconsole.log(linked.isEmpty()); // false