前言与链表实现数组

缘起

最近工作上需要依照现有数据生成嵌套json对象形式的组织机构列表&＃xff0c;一时觉得无从下手&＃xff0c;请教同事大神才知道此乃数据结构相关知识&＃xff0c;遂恶补相关基础并在此记录。

数据结构可以分为&＃xff1a;1、列表&＃xff1b;2、线性&＃xff1b;3、树形&＃xff1b;4、图 四种基本结构。何为数据结构&＃xff1f;我理解就是数据的结构。。。即承载数据的形式。数据结构中的线性结构有数组和链表&＃xff0c;本文即对链表进行简单总结&＃xff0c;在后续文章中会实现几种基本的数据结构。

链表

1 链表是什么

链表相关概念

2 用链表实现数组和其基本操作&＃xff0c;以下附上代码

function ARRAY(){var INDEX&＃61;-1;var HEAD&＃61;null;var OBJ&＃61;null;//添加元素this.add&＃61;function(e){function Element(value){this.value&＃61;value;}e&＃61;new Element(e);if(INDEX&＃61;&＃61;-1){OBJ&＃61;e;HEAD&＃61;e;INDEX&＃43;&＃43;;}else{INDEX&＃43;&＃43;;OBJ.next&＃61;e;OBJ&＃61;OBJ.next;}return HEAD;}//删除最后一个元素this.deleteLast&＃61;function(){for(var i&＃61;HEAD;i!&＃61;undefined;i&＃61;i.next){if(i.next.next&＃61;&＃61;undefined){i.next&＃61;null;}}return HEAD;}//按序号取元素this.get&＃61;function(Inx){var index&＃61;0;for(var i&＃61;HEAD;i!&＃61;undefined;i&＃61;i.next){index&＃43;&＃43;;if(index&＃61;&＃61;Inx){return i;}}}//按位置插入元素this.insert&＃61;function(Inx,e){function Element(value){this.value&＃61;value;}e&＃61;new Element(e);if(Inx&＃61;&＃61;0){e.next&＃61;HEAD;HEAD&＃61;e;}else{var currentItem&＃61;this.get(Inx);var sufItem&＃61;this.get(Inx&＃43;1);e.next&＃61;sufItem;currentItem.next&＃61;e;}return HEAD;}//删除特定位置元素this.deleteElement&＃61;function(Inx){if(Inx&＃61;&＃61;0){var sufItem&＃61;this.get(Inx&＃43;1);HEAD&＃61;sufItem;}else{var preItem&＃61;this.get(Inx-1);var sufItem&＃61;this.get(Inx&＃43;1);preItem.next&＃61;sufItem;}return HEAD;}
}

同时提供两种遍历链表的方法

//遍历链表&＃xff08;递归&＃xff09;
function loop(head){if(head.next&＃61;&＃61;undefined){return;}return loop(head.next);
}

//遍历链表&＃xff08;非递归&＃xff09;
function loopLinkedList(head){for(var i&＃61;head;i!&＃61;undefined;i&＃61;i.next){console.log(i);}
}

具体使用方法

var obj &＃61; new ARRAY();
console.time(&＃39;addtest&＃39;);
obj.add(&＃39;aaa&＃39;);
obj.add(&＃39;bbb&＃39;);
obj.add(&＃39;ccc&＃39;);
obj.add(&＃39;ddd&＃39;);
var head&＃61;obj.add(&＃39;eee&＃39;);
console.log(head);
console.timeEnd(&＃39;addtest&＃39;);