第5章 链表
2016-11-01 本文已影响4人
不系流年系乾坤
队列
function LinkedList() {
let Node = function(element){
this.element = element;
this.next = null;
};
let length = 0;
let head = null;
this.append = function(element){
let node = new Node(element),
current;
if (head === null){ //first node on list
head = node;
} else {
current = head;
//loop the list until find last item
while(current.next){
current = current.next;
}
//get last item and assign next to added item to make the link
current.next = node;
}
length++; //update size of list
};
this.insert = function(position, element){
//check for out-of-bounds values
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0){ //add on first position
node.next = current;
head = node;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++; //update size of list
return true;
} else {
return false;
}
};
this.removeAt = function(position){
//check for out-of-bounds values
if (position > -1 && position < length){
let current = head,
previous,
index = 0;
//removing first item
if (position === 0){
head = current.next;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
//link previous with current's next - skip it to remove
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};
this.remove = function(element){
let index = this.indexOf(element);
return this.removeAt(index);
};
this.indexOf = function(element){
let current = head,
index = 0;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
};
this.isEmpty = function() {
return length === 0;
};
this.size = function() {
return length;
};
this.getHead = function(){
return head;
};
this.toString = function(){
let current = head,
string = '';
while (current) {
string += current.element + (current.next ? ', ' : '');
current = current.next;
}
return string;
};
this.print = function(){
console.log(this.toString());
};
}
LinkedList2
let LinkedList2 = (function () {
class Node {
constructor(element){
this.element = element;
this.next = null;
}
}
const length = new WeakMap();
const head = new WeakMap();
class LinkedList2 {
constructor () {
length.set(this, 0);
head.set(this, null);
}
append(element) {
let node = new Node(element),
current;
if (this.getHead() === null) { //first node on list
head.set(this, node);
} else {
current = this.getHead();
//loop the list until find last item
while (current.next) {
current = current.next;
}
//get last item and assign next to added item to make the link
current.next = node;
}
//update size of list
let l = this.size();
l++;
length.set(this, l);
}
insert(position, element) {
//check for out-of-bounds values
if (position >= 0 && position <= this.size()) {
let node = new Node(element),
current = this.getHead(),
previous,
index = 0;
if (position === 0) { //add on first position
node.next = current;
head.set(this, node);
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
//update size of list
let l = this.size();
l++;
length.set(this, l);
return true;
} else {
return false;
}
}
removeAt(position) {
//check for out-of-bounds values
if (position > -1 && position < this.size()) {
let current = this.getHead(),
previous,
index = 0;
//removing first item
if (position === 0) {
head.set(this, current.next);
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
//link previous with current's next - skip it to remove
previous.next = current.next;
}
let l = this.size();
l--;
length.set(this, l);
return current.element;
} else {
return null;
}
}
remove(element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
indexOf(element) {
let current = this.getHead(),
index = 0;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
}
isEmpty() {
return this.size() === 0;
}
size() {
return length.get(this);
}
getHead() {
return head.get(this);
}
toString() {
let current = this.getHead(),
string = '';
while (current) {
string += current.element + (current.next ? ', ' : '');
current = current.next;
}
return string;
}
print() {
console.log(this.toString());
}
}
return LinkedList2;
})();
use
let list = new LinkedList2();
list.append(15);
list.print();
console.log(list.indexOf(15));
list.append(10);
list.print();
console.log(list.indexOf(10));
list.append(13);
list.print();
console.log(list.indexOf(13));
console.log(list.indexOf(10));
list.append(11);
list.append(12);
list.print();
console.log(list.removeAt(1));
list.print()
console.log(list.removeAt(3));
list.print();
list.append(14);
list.print();
list.insert(0,16);
list.print();
list.insert(1,17);
list.print();
list.insert(list.size(),18);
list.print();
list.remove(16);
list.print();
list.remove(11);
list.print();
list.remove(18);
list.print();
双向链表
function DoublyLinkedList() {
let Node = function(element){
this.element = element;
this.next = null;
this.prev = null; //NEW
};
let length = 0;
let head = null;
let tail = null; //NEW
this.append = function(element){
let node = new Node(element),
current;
if (head === null){ //first node on list
head = node;
tail = node; //NEW
} else {
//attach to the tail node //NEW
tail.next = node;
node.prev = tail;
tail = node;
}
length++; //update size of list
};
this.insert = function(position, element){
//check for out-of-bounds values
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0){ //add on first position
if (!head){ //NEW
head = node;
tail = node;
} else {
node.next = current;
current.prev = node; //NEW {1}
head = node;
}
} else if (position === length) { //last item //NEW
current = tail; // {2}
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position){ //{3}
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node; //NEW
node.prev = previous; //NEW
}
length++; //update size of list
return true;
} else {
return false;
}
};
this.removeAt = function(position){
//check for out-of-bounds values
if (position > -1 && position < length){
let current = head,
previous,
index = 0;
//removing first item
if (position === 0){
head = current.next; // {1}
//if there is only one item, then we update tail as well //NEW
if (length === 1){ // {2}
tail = null;
} else {
head.prev = null; // {3}
}
} else if (position === length-1){ //last item //NEW
current = tail; // {4}
tail = current.prev;
tail.next = null;
} else {
while (index++ < position){ // {5}
previous = current;
current = current.next;
}
//link previous with current's next - skip it to remove
previous.next = current.next; // {6}
current.next.prev = previous; //NEW
}
length--;
return current.element;
} else {
return null;
}
};
this.remove = function(element){
let index = this.indexOf(element);
return this.removeAt(index);
};
this.indexOf = function(element){
let current = head,
index = -1;
//check first item
if (element == current.element){
return 0;
}
index++;
//check in the middle of the list
while(current.next){
if (element == current.element){
return index;
}
current = current.next;
index++;
}
//check last item
if (element == current.element){
return index;
}
return -1;
};
this.isEmpty = function() {
return length === 0;
};
this. size = function() {
return length;
};
this.toString = function(){
let current = head,
s = current ? current.element : '';
while(current && current.next){
current = current.next;
s += ', ' + current.element;
}
return s;
};
this.inverseToString = function() {
let current = tail,
s = current ? current.element : '';
while(current && current.prev){
current = current.prev;
s += ', ' + current.element;
}
return s;
};
this.print = function(){
console.log(this.toString());
};
this.printInverse = function(){
console.log(this.inverseToString());
};
this.getHead = function(){
return head;
};
this.getTail = function(){
return tail;
}
}
DoublyLinkedList2
let DoublyLinkedList2 = (function () {
class Node {
constructor(element) {
this.element = element;
this.next = null;
this.prev = null; //NEW
}
}
const length = new WeakMap();
const head = new WeakMap();
const tail = new WeakMap(); //NEW
class DoublyLinkedList2 {
constructor () {
length.set(this, 0);
head.set(this, null);
tail.set(this, null);
}
append(element) {
let node = new Node(element),
current, _tail;
if (this.getHead() === null) { //first node on list
head.set(this, node);
tail.set(this, node); //NEW
} else {
//attach to the tail node //NEW
_tail = this.getTail();
_tail.next = node;
node.prev = _tail;
tail.set(this, node);
}
//update size of list
let l = this.size();
l++;
length.set(this, l);
}
insert(position, element) {
//check for out-of-bounds values
if (position >= 0 && position <= this.size()) {
let node = new Node(element),
current = this.getHead(),
previous,
index = 0;
if (position === 0) { //add on first position
if (!this.getHead()) { //NEW
head.set(this, node);
tail.set(this, node);
} else {
node.next = current;
current.prev = node; //NEW {1}
head.set(this, node);
}
} else if (position === this.size()) { //last item //NEW
current = tail; // {2}
current.next = node;
node.prev = current;
tail.set(this, node);
} else {
while (index++ < position) { //{3}
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node; //NEW
node.prev = previous; //NEW
}
//update size of list
let l = this.size();
l++;
length.set(this, l);
return true;
} else {
return false;
}
}
removeAt(position) {
//check for out-of-bounds values
if (position > -1 && position < this.size()) {
let _head = this.getHead(),
_tail = this.getTail(),
current = _head,
previous,
index = 0;
//removing first item
if (position === 0) {
_head = current.next; // {1}
//if there is only one item, then we update tail as well //NEW
if (this.size() === 1) { // {2}
_tail = null;
} else {
_head.prev = null; // {3}
}
} else if (position === this.size() - 1) { //last item //NEW
current = _tail; // {4}
_tail = current.prev;
_tail.next = null;
} else {
while (index++ < position) { // {5}
previous = current;
current = current.next;
}
//link previous with current's next - skip it to remove
previous.next = current.next; // {6}
current.next.prev = previous; //NEW
}
head.set(this,_head);
tail.set(this,_tail);
//update size of list
let l = this.size();
l--;
length.set(this, l);
return current.element;
} else {
return null;
}
}
remove(element) {
let index = this.indexOf(element);
return this.removeAt(index);
}
indexOf(element) {
let current = this.getHead(),
index = -1;
//check first item
if (element == current.element) {
return 0;
}
index++;
//check in the middle of the list
while (current.next) {
if (element == current.element) {
return index;
}
current = current.next;
index++;
}
//check last item
if (element == current.element) {
return index;
}
return -1;
}
isEmpty() {
return this.size() === 0;
}
size() {
return length.get(this);
}
toString() {
let current = this.getHead(),
s = current ? current.element : '';
while (current && current.next) {
current = current.next;
s += ', ' + current.element;
}
return s;
}
inverseToString() {
let current = this.getTail(),
s = current ? current.element : '';
while (current && current.prev) {
current = current.prev;
s += ', ' + current.element;
}
return s;
}
print() {
console.log(this.toString());
}
printInverse() {
console.log(this.inverseToString());
}
getHead() {
return head.get(this);
}
getTail() {
return tail.get(this);
}
}
return DoublyLinkedList2;
})();
use
let list = new DoublyLinkedList2();
list.append(15);
list.print();
list.printInverse();
list.append(16);
list.print();
list.printInverse();
list.append(17);
list.print();
list.printInverse();
list.insert(0,13);
list.print();
list.printInverse();
list.insert(4,18);
list.print();
list.printInverse();
list.insert(1,14);
list.print();
list.printInverse();
list.removeAt(0);
list.print();
list.printInverse();
list.removeAt(list.size()-1);
list.print();
list.printInverse();
list.removeAt(1);
list.print();
list.printInverse();
list.remove(16);
list.print();
list.printInverse();
list.remove(14);
list.print();
list.printInverse();
list.remove(17);
list.print();
list.printInverse();
循环链表
function CircularLinkedList() {
let Node = function(element){
this.element = element;
this.next = null;
};
let length = 0;
let head = null;
this.append = function(element){
let node = new Node(element),
current;
if (head === null){ //first node on list
head = node;
} else {
current = head;
//loop the list until find last item
while(current.next !== head){ //last element will be head instead of NULL
current = current.next;
}
//get last item and assign next to added item to make the link
current.next = node;
}
//set node.next to head - to have circular list
node.next = head;
length++; //update size of list
};
this.insert = function(position, element){
//check for out-of-bounds values
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0){ //add on first position
node.next = current;
//update last element
while(current.next !== head){ //last element will be head instead of NULL
current = current.next;
}
head = node;
current.next = head;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++; //update size of list
return true;
} else {
return false;
}
};
this.removeAt = function(position){
//check for out-of-bounds values
if (position > -1 && position < length){
let current = head,
previous,
index = 0;
//removing first item
if (position === 0){
while(current.next !== head){ //needs to update last element first
current = current.next;
}
head = head.next;
current.next = head;
} else { //no need to update last element for circular list
while (index++ < position){
previous = current;
current = current.next;
}
//link previous with current's next - skip it to remove
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};
this.remove = function(element){
let index = this.indexOf(element);
return this.removeAt(index);
};
this.indexOf = function(element){
let current = head,
index = -1;
//check first item
if (element == current.element){
return 0;
}
index++;
//check in the middle of the list
while(current.next !== head){
if (element == current.element){
return index;
}
current = current.next;
index++;
}
//check last item
if (element == current.element){
return index;
}
return -1;
};
this.isEmpty = function() {
return length === 0;
};
this.size = function() {
return length;
};
this.getHead = function(){
return head;
};
this.toString = function(){
let current = head,
s = current.element;
while(current.next !== head){
current = current.next;
s += ', ' + current.element;
}
return s.toString();
};
this.print = function(){
console.log(this.toString());
};
}
CircularLinkedList2
let CircularLinkedList2 = (function () {
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
const length = new WeakMap();
const head = new WeakMap();
class CircularLinkedList2 {
constructor () {
length.set(this, 0);
head.set(this, null);
}
append(element) {
let node = new Node(element),
current;
if (this.getHead() === null) { //first node on list
head.set(this, node);
} else {
current = this.getHead();
//loop the list until find last item
while (current.next !== this.getHead()) { //last element will be head instead of NULL
current = current.next;
}
//get last item and assign next to added item to make the link
current.next = node;
}
//set node.next to head - to have circular list
node.next = this.getHead();
//update size of list
let l = this.size();
l++;
length.set(this, l);
}
insert(position, element) {
//check for out-of-bounds values
if (position >= 0 && position <= this.size()) {
let node = new Node(element),
current = this.getHead(),
previous,
index = 0;
if (position === 0) { //add on first position
node.next = current;
//update last element
while (current.next !== this.getHead()) { //last element will be head instead of NULL
current = current.next;
}
head.set(this, node);
current.next = this.getHead();
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
//update size of list
let l = this.size();
l++;
length.set(this, l);
return true;
} else {
return false;
}
}
removeAt(position) {
//check for out-of-bounds values
if (position > -1 && position < this.size()) {
let current = this.getHead(),
previous,
index = 0;
//removing first item
if (position === 0) {
while (current.next !== this.getHead()) { //needs to update last element first
current = current.next;
}
head.set(this, this.getHead().next);
current.next = this.getHead();
} else { //no need to update last element for circular list
while (index++ < position) {
previous = current;
current = current.next;
}
//link previous with current's next - skip it to remove
previous.next = current.next;
}
let l = this.size();
l--;
length.set(this, l);
return current.element;
} else {
return null;
}
}
remove(element) {
let index = indexOf(element);
return removeAt(index);
}
indexOf(element) {
let current = this.getHead(),
index = -1;
//check first item
if (element == current.element) {
return 0;
}
index++;
//check in the middle of the list
while (current.next !== this.getHead()) {
if (element == current.element) {
return index;
}
current = current.next;
index++;
}
//check last item
if (element == current.element) {
return index;
}
return -1;
}
isEmpty() {
return this.size() === 0;
}
size() {
return length.get(this);
}
getHead() {
return head.get(this);
}
toString() {
let current = this.getHead(),
s = current.element;
while (current.next !== this.getHead()) {
current = current.next;
s += ', ' + current.element;
}
return s.toString();
}
print() {
console.log(this.toString());
}
}
return CircularLinkedList2;
})();
use
let circularLinkedList = new CircularLinkedList2();
circularLinkedList.append(15);
circularLinkedList.print();
circularLinkedList.append(16);
circularLinkedList.print();
circularLinkedList.insert(0,14);
circularLinkedList.print();
circularLinkedList.insert(1,14.5);
circularLinkedList.print();
circularLinkedList.insert(4,17);
circularLinkedList.print();
circularLinkedList.removeAt(0);
circularLinkedList.print();
circularLinkedList.removeAt(1);
circularLinkedList.print();
circularLinkedList.removeAt(2);
circularLinkedList.print();
console.log(circularLinkedList.indexOf(14.5));
console.log(circularLinkedList.indexOf(16));
