目录
链表
链表的封装
function LinkList() {
// 内部的类：节点类
function Node(data) {
this.data = data;
this.next = null;
}
this.head = null;
this.length = 0;
LinkList.prototype.append = function (data) {
var newNode = new Node(data);
if (this.length == 0) {
this.head = newNode;
}else{
var current = this.head;
while(current.next){
current = current.next;
}
current.next = newNode;
}
this.length += 1;
}
LinkList.prototype.toString = function () {
var current = this.head;
var listString = '';
while(current){
listString += current.data + ' ';
current = current.next;
}
return listString;
}
LinkList.prototype.insert = function (position, data) {
if ( position < 0 || position > this.length) return false;
var newNode = new Node(data);
if (position == 0) {
newNode.next = this.head;
this.head = newNode;
}else{
var index = 0;
var current = this.head;
var previous = null;
// while(index ++ < position){
// previous = current;
// current = current.next;
// }
// newNode.next = current;
// previous.next = newNode;
while(index ++ < position - 1){
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
// 上下两种是一样的
}
this.length += 1
return true;
}
LinkList.prototype.get = function (position) {
if (position < 0 || position >= this.length) return null;
var current =this.head;
var index = 0;
while(index++ < position){
current = current.next;
}
return current.data;
}
LinkList.prototype.indexOf = function (data) {//返回元素在列表中的索引，没有返回-1
var current = this.head;
var index = 0;
while(current){
index ++;
if (current.data == data) {
return index;
}
current = current.next;
}
return -1;
}
LinkList.prototype.upDate = function (position, data) {//修改某个位置的元素
var current = this.head;
var index = 0;
if (position < 0 || position >= this.length) return false;
while(index ++ < position){
current = current.next;
}
current.data = data;
return true;
}
LinkList.prototype.removeAt = function (position) {//移除指定位置的元素结点
var current = this.head;
var pre;
var index = 0;
if (position < 0 || position >= this.length) return null;
if (position == 0) {
this.head = this.head.next;
}else{
while(index++ < position){
pre = current;
current = current.next;
}
pre.next = current.next;
}
this.length -= 1;
return current.data;
}
LinkList.prototype.remove = function (element) {//移除确定元素的结点
// var position = this.indexOf(element) - 1;
// this.removeAt(position);
var current = this.head;
var pre = null;
for(var i = 0; i < this.length; i++){
if (current.data == element) {
if (current == this.head) {
this.head = this.head.next;
}else{
pre.next = current.next;
}
break;
}
pre = current;
current = current.next;
}
this.length -= 1;
// 两种办法都可以
}
LinkList.prototype.isEmpty = function () {
return this.length == 0;
}
LinkList.prototype.size = function () {
return this.length;
}
}
双向链表
是既可以从头遍历到尾，又可以从尾遍历到头
一个节点既有向前连接的引用，也有向后连接的引用
小缺点：再每次插入或删除节点的时候，要处理四个引用
function DoublyLinked() {
function Node(data) {
this.data = data;
this.prev = null;
this.next = null;
}
this.head = null;
this.tail = null;
this.length = 0;
DoublyLinked.prototype.append = function (data) {
let newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
}else{
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
this.length ++;
}
DoublyLinked.prototype.insert = function (position, element) {
let newNode = new Node(element);
let current = this.head;
let index = 0;
if (position < 0 || position > this.length) return false;
if (this.length == 0) {
this.head = newNode;
this.tail = newNode;
}else{//有三种情况，主要还是既有head还有tail
if (position == 0) {
this.head.prev = newNode;
newNode.next = this.head;
this.head = newNode;
}else if (this.length == position) {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}else{
while(index ++ < position){
current = current.next;
}//其实是插在current的前面
current.prev.next = newNode;
newNode.next = current;
newNode.prev = current.prev;
current.prev = newNode;
}
}
this.length ++;
return true;
}
DoublyLinked.prototype.get = function (position) {
let current = this.head;
let index = 0;
if (position < 0 || position >= this.length) return null;
while(index++ < position){
current = current.next;
}
return current.data;
}
DoublyLinked.prototype.indexOf = function (element) {
let current = this.head;
for (let i = 0; i < this.length; i++) {
if (current.data == element) {
return i;
}
current = current.next;
}
return -1;
}
DoublyLinked.prototype.upDate = function (position, element) {//修改这个地方的data
let index = 0;
if (position < 0 || position >= this.length) return false;
if (position < this.length/2) {//这里是循环的优化，减少时间复杂度，get方法也可以用
let current = this.head;
while(index ++ < position){
current = current.next;
}
current.data = element;
}else{
let current = this.tail;
index = this.length - 1;
while(index-- > position){
current = current.prev;
}
current.data = element;
}
}
DoublyLinked.prototype.removeAt = function (position) {
if (position < 0 || position >= this.length) return false;
let current = this.head;
let index = 0;
if(this.length == 1){
this.head = null;
this.tail = null;
}else {
if (position == 0) {
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{
while(index ++ < position){
current = current.next;
}
current.next.prev = current.prev;
current.prev.next = current.next;
}
}
this.length --;
return current.data;
}
DoublyLinked.prototype.remove = function (element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
DoublyLinked.prototype.toString = function () {
return this.backwardString();
}
DoublyLinked.prototype.forwardString = function () {
let current = this.tail;
let resstr = '';
while(current){
resstr += current.data + ' ';
current = current.prev;
}
return resstr;
}
DoublyLinked.prototype.backwardString = function () {
let current = this.head;
let resstr = '';
while(current){
resstr += current.data + ' ';
current = current.next;
}
return resstr;
}
DoublyLinked.prototype.isEmpty = function () {
return this.length == 0;
}
DoublyLinked.prototype.size = function () {
return this.length;
}
DoublyLinked.prototype.getHead = function () {
return this.head;
}
DoublyLinked.prototype.getTail = function () {
return this.tail;
}
}