在上一篇文章中浦徊，我們說到了棧與隊列绍赛，這章中，我們來看看另一個基礎(chǔ)的知識辑畦，鏈表
鏈表
鏈表是存儲的有序元素的集合吗蚌，但是不同于數(shù)組連續(xù)存儲方式，鏈表在存儲中并不是采用連續(xù)放置的方式纯出，而是每一個元素由節(jié)點(diǎn)和指向下一個元素的引用（其他語言中的指針）蚯妇。所以我們可以得知鏈表的具體的形式應(yīng)該是![鏈表]
image.png
那么我們將上圖進(jìn)行拆分，我們可以很明確的得到一個鏈表應(yīng)該有的數(shù)據(jù)結(jié)構(gòu)暂筝，如下圖：
image.png
從上圖可以得知箩言，一個鏈表我們可以將其拆分List類，和node類焕襟。所以我們可以先實現(xiàn)這兩個類
Node類
/**
* @export
* @class LinkNode
*/
export default class LinkNode {
[x: string]: undefined;
public node:any;
public next: undefined;
constructor(node:any) {
this.node = node;
this.next = undefined;
}
}
List類
*
* @export
* @class LinkList
*/
import LinkNode from './LinkNode'
export default class LinkList {
public count: number;
public head: any | undefined;
constructor() {
this.count = 0;
this.head = undefined;
}
}
那么一個鏈表應(yīng)該需要哪些方法呢陨收？從個人理解中，同隊列和棧一樣需要以下方法
| 方法名 | 描述 |
|---|---|
| push(item) | 添加一個元素到鏈表中 |
| insert(item,index) | 添加一個元素到鏈表指定位置中 |
| getItemAt(index) | 獲取鏈表指定位置元素 |
| remove() | 移除最后一項 |
| clear() | 清除鏈表 |
| size() | 返回鏈表大小 |
| removeAt(index) | 移除指定位置元素并返回 |
| indexOf(item) | 獲取指定元素所在的位置 |
下面我們來一一分析上面方法的具體實現(xiàn)
Push
向鏈尾添加元素鸵赖。那么有兩種情況务漩，一種是最初始狀態(tài)下添加，根據(jù)我們前面的list類它褪，我們可以看出饵骨，當(dāng)前數(shù)據(jù)格式為，也就是一個head指向的是undefined茫打。那么我們添加一個數(shù)據(jù)后居触，我們的數(shù)據(jù)格式應(yīng)該為什么樣呢，第二種情況為在已有的數(shù)據(jù)格式的基礎(chǔ)下添加老赤，那么我們可以思考下怎么實現(xiàn)呢轮洋？
我們來分析下，也就是當(dāng)前最后一個變成了倒數(shù)第二個抬旺，push進(jìn)來的node為最后一個弊予，所以只需要將當(dāng)前最后一個的next指向當(dāng)前傳入的即可。如圖
push方法分析
因此Push方法就此實現(xiàn)
/**
*尾部插入元素
*
* @param {*} item
* @memberof LinkList
*/
public push(item: any) {
let node = new LinkNode(item);
// 將節(jié)點(diǎn)的head設(shè)置成node
if (!this.head) {
this.head = node;
} else {
// 如果不是空嚷狞，則需要找到鏈表最后一個node块促，然后將最后一個節(jié)點(diǎn)的next設(shè)置成當(dāng)前傳入的node
let currentNode: any = this.getItemAt(this.count - 1);
currentNode.next = node;
}
this.count++;
}
removeAt（index）
從指定位置移除元素。我們可以先來分析下床未，移除有三種情況
image.png
第二種移除尾部，類比移除頭部，只需要將倒數(shù)第二個節(jié)點(diǎn)的next指向為undefined即可传货，如圖
image.png
第三種就是刪除中間位置屎鳍，同理只需要將index所處的節(jié)點(diǎn)前一個節(jié)點(diǎn)的next指向index所處節(jié)點(diǎn)的next節(jié)點(diǎn)即可
image.png
具體實現(xiàn)如下
/**
* 移除指定位置的節(jié)點(diǎn)
* @param {number} index
* @returns {LinkNode}
* @memberof LinkList
*/
public removeAt(index: number): LinkNode | undefined {
if (index >= 0 && index <= this.count) {
let cuttentNode: LinkNode = this.getItemAt(index);
if (index === this.count - 1) {
let pretNode: LinkNode = this.getItemAt(index - 1);
pretNode.next = undefined;
} else if (index === 0) {
let headNode: LinkNode = this.getItemAt(0);
headNode.head = undefined;
} else {
let preNode: LinkNode = this.getItemAt(index - 1);
let currentNode: LinkNode = this.getItemAt(index);
preNode.next = currentNode.next;
}
this.count--;
return cuttentNode;
}
return undefined;
}
insert（item,index)
在指定位置插入元素。我們來分析分析问裕，我們選擇插入元素逮壁，那么同移除有三個位置，頭部粮宛，尾部以及中間
image.png
第二種情況，從尾部插入筷畦，也就是將當(dāng)前尾部元素的next指向我們插入的元素词裤，我們插入的元素的next指向原有元素next指向的位置
image.png
第三種情況插入中間位置，那么也就是說假設(shè)我們將數(shù)據(jù)插入第二個位置鳖宾，我們只需要將第一個位置節(jié)點(diǎn)的next指向插入的元素吼砂，插入的元素的next指向當(dāng)前元素即可。如圖
image.png
這個時候我們再回顧下從尾部插入攘滩，我們是否也可以跟中間節(jié)點(diǎn)一樣帅刊，將最后一個節(jié)點(diǎn)的前一個節(jié)點(diǎn)的next賦值給當(dāng)前節(jié)點(diǎn)的next,前一個節(jié)點(diǎn)的next指向插入的節(jié)點(diǎn)，貌似也行漂问，那么代碼實現(xiàn)為。
/**
* 任意位置插入元素
* @param {*} item
* @param {number} index
* @returns {boolean}
* @memberof LinkList
*/
public insert(item: any, index: number): boolean {
if (index >= 0 && index <= this.count) {
let node = new LinkNode(item);
if (index === 0) {
let currentNode = this.head;
node.next = currentNode;
this.head = node;
} else {
let preNode = this.getItemAt(index - 1);
node.next = preNode.next;
preNode.next = node;
}
this.count++;
return true;
}
return false;
}
至此一個普通鏈表的最重要的三個方法講完了女揭，下面附上一個鏈表的具體的實現(xiàn).下一章我們進(jìn)入另一個鏈表-雙向鏈表
/**
* push
* insert
* getItemAt
* remove
* indexOf
* removeAt
* isEmpty
* size
*
*
* @export
* @class LinkList
*/
import LinkNode from './LinkNode'
export default class LinkList {
public count: number;
public head: any | undefined;
constructor() {
this.count = 0;
this.head = undefined;
}
/**
*尾部插入元素
*
* @param {*} item
* @memberof LinkList
*/
public push(item: any) {
let node = new LinkNode(item);
// 將節(jié)點(diǎn)的head設(shè)置成node
if (!this.head) {
this.head = node;
} else {
// 如果不是空蚤假，則需要找到鏈表最后一個node，然后將最后一個節(jié)點(diǎn)的next設(shè)置成當(dāng)前傳入的node
let currentNode: any = this.getItemAt(this.count - 1);
currentNode.next = node;
}
this.count++;
}
/**
* 任意位置插入元素
* @param {*} item
* @param {number} index
* @returns {boolean}
* @memberof LinkList
*/
public insert(item: any, index: number): boolean {
if (index >= 0 && index <= this.count) {
let node = new LinkNode(item);
if (index === 0) {
let currentNode = this.head;
node.next = currentNode;
this.head = node;
} else {
let preNode = this.getItemAt(index - 1);
node.next = preNode.next;
preNode.next = node;
}
this.count++;
return true;
}
return false;
}
/**
* 移除指定位置的節(jié)點(diǎn)
* @param {number} index
* @returns {LinkNode}
* @memberof LinkList
*/
public removeAt(index: number): LinkNode | undefined {
if (index >= 0 && index <= this.count) {
let cuttentNode: LinkNode = this.getItemAt(index);
if (index === this.count - 1) {
let pretNode: LinkNode = this.getItemAt(index - 1);
pretNode.next = undefined;
} else if (index === 0) {
let headNode: LinkNode = this.getItemAt(0);
headNode.head = undefined;
} else {
let preNode: LinkNode = this.getItemAt(index - 1);
let currentNode: LinkNode = this.getItemAt(index);
preNode.next = currentNode.next;
}
this.count--;
return cuttentNode;
}
return undefined;
}
/**
* 獲取指定位置的節(jié)點(diǎn)
* @param {number} index
* @returns {(LinkNode|undefined)}
* @memberof LinkList
*/
public getItemAt(index: number): LinkNode | undefined | any {
if (index >= 0) {
if (index > this.count) {
return undefined;
} else if (index === 0) {
return this.head;
} else {
let currentNode = this.head;
while (index && currentNode.next) {
currentNode = currentNode.next;
index--;
}
return currentNode;
}
}
}
/**
* 返回item所在的位置
* @param {*} item
* @returns {number}
* @memberof LinkList
*/
public indexOf(item: any): number {
let currentNode = this.head;
let hasFind: boolean = false;
let index: number = -1;
while (!hasFind && currentNode) {
index++;
if (this.judgeObjectSame(item, currentNode.node)) {
hasFind = true;
} else {
currentNode = currentNode.next;
}
}
if (hasFind) {
return index;
} else {
return -1;
}
}
/**
* 移除指定元素
* @param {*} item
* @memberof LinkList
*/
public remove(item: any) {
let index = this.indexOf(item);
this.removeAt(index);
}
/**
* 獲取鏈表size
* @returns {number}
* @memberof LinkList
*/
public size(): number {
return this.count;
}
/**
* 判斷是否為空
* @returns
* @memberof LinkList
*/
public isEmpty() {
return this.size() === 0;
}
/**
* 判斷兩個對象是否相同
*
* @param {*} firstObj
* @param {*} secondObj
* @returns
* @memberof StackObject
*/
public judgeObjectSame(firstObj: any, secondObj: any) {
const aProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(firstObj)));
const bProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(secondObj)));
if (aProps.length !== bProps.length) {
return false;
}
for (let i = 0; i < aProps.length; i++) {
const propName = aProps[i]
const propA = firstObj[propName]
const propB = secondObj[propName]
if ((typeof (propA) === 'object') && propA !== null) {
if (this.judgeObjectSame(propA, propB)) {
} else {
return false;
}
} else if (propA !== propB) {
return false;
} else { }
}
return true;
}
}
