1、单项循环链表：
class Cnode {
constructor(data) {
this.data = data;
this.next = null;
}
}
class CycleLinkList {
constructor() {
this.head = null;
this.len = 0
}
// 1.向链表最后添加元素
append(ele) {
let newnode = new Cnode(ele);
if (this.head == null) { //空链表
this.head = newnode;
newnode.next = this.head;
} else { //非空链表
// 需要找到最后一个节点 最后一个节点.next指向头节点
let current = this.head;
while (current.next != this.head) {
//继续往下找
current = current.next;
}
// 找到了,cuurent表示最后一个节点
current.next = newnode;
newnode.next = this.head;
}
this.len++
}
// 2.向链表中插入元素
insert(position, ele) {
if (position < 0 || position > this.len || !Number.isInteger(position)) return
let newnode = new Cnode(ele);
let current = this.head,
index = 0;
if (position == 0) {
if (this.len == 0) {
this.head = newnode;
newnode.next = this.head;
} else {
while (current.next != this.head) {
current = current.next;
}
newnode.next = this.head;
current.next = newnode;
this.head = newnode;
}
this.len++
} else if (position == this.len) {
this.append(ele)
} else {
while (index < position - 1) {
current = current.next;
index++;
}
newnode.next = current.next;
current.next = newnode;
this.len++
}
}
// 3.removeAt(position) 移除指定位置的元素
removeAt(position) {
if (position < 0 || position > this.len - 1 || !Number.isInteger(position)) return
let current = this.head,
index = 0;
if (position == 0) {
if (this.len == 1) {
this.head = null;
} else {
while (current.next != this.head) {
current = current.next;
}
this.head = this.head.next;
current.next = this.head;
}
}else{
while (index < position - 1) {
current = current.next;
index++;
}
current.next = current.next.next
}
this.len--
}
// 4.查找指定元素
indexOf(ele){
let current = this.head,index=0;
while(index < this.len){
if(current.data == ele){
return index
}else{
current = current.next;
index++
}
}
return -1
}
// 5.移除指定元素
remove(ele){
this.removeAt(this.indexOf(ele))
}
toString() {
let current = this.head,
index = 0,
res = "";
while (index < this.len) {
res += "-" + current.data;
current = current.next;
index++;
}
return res.slice(1)
}
}
let clist = new CycleLinkList();
for (let i = 0; i < 9; i++) {
clist.append(i)
}
console.log(clist.indexOf("hello"));
console.log(clist.indexOf(0));
clist.remove("hello")
clist.remove(6)
console.log(clist.toString());2、双项循环链表：
class Node {
constructor(data) {
this.prev = null;
this.data = data;
this.next = null;
}
}
class CycleDoubleLinkList {
constructor() {
this.head = null;
this.tail = null;
this.len = 0;
}
// 1.向链表最后添加元素
append(ele) {
let newnode = new Node(ele);
if (this.len == 0) {
//空链表
this.head = newnode;
this.tail = newnode;
newnode.prev = this.tail;
newnode.next = this.head;
} else {
// 将新节点连接
newnode.prev = this.tail;
newnode.next = this.head;
// 断开原来的指向,重新指向新节点
this.tail.next = newnode;
this.head.prev = newnode;
this.tail = newnode;
}
this.len++
}
// 2.向链表中的指定位置插入元素
insert(position, ele) {
if (position < 0 || position > this.len || !Number.isInteger(position)) return
let newnode = new Node(ele);
if (position == 0) {
if (this.len == 0) {
//空链表
this.head = newnode;
this.tail = newnode;
newnode.prev = this.tail;
newnode.next = this.head;
} else {
newnode.prev = this.tail;
newnode.next = this.head;
this.head.prev = newnode
this.tail.next = newnode;
this.head = newnode;
}
this.len++
}else if(position == this.len){
this.append(ele)
}else{
let current = this.head,index = 0;
while(index< position-1){
current = current.next;
index++;
}
newnode.prev = current;
newnode.next = current.next;
current.next = newnode;
newnode.next.prev = newnode;
this.len++
}
}
// 3.移除指定位置的元素
removeAt(position){
if (position < 0 || position > this.len-1 || !Number.isInteger(position)) return
if(position == 0){
if(this.len == 1){
this.head = null;
this.tail = null;
}else{
this.head = this.head.next;
this.tail.next = this.head;
this.head.prev = this.tail;
}
}else if(position == this.len-1){
this.tail = this.tail.prev;
this.tail.next = this.head;
this.head.prev = this.tail;
}else{
let current = this.head,index= 0;
while(index < position-1){
current = current.next;
index++;
}
current.next = current.next.next;
current.next.prev = current
}
this.len--
}
// 4.查找
// 4.查找指定元素
indexOf(ele){
let current = this.head,index=0;
while(index < this.len){
if(current.data == ele){
return index
}else{
current = current.next;
index++
}
}
return -1
}
// 5.移除指定元素
remove(ele){
this.removeAt(this.indexOf(ele))
}
toAfterString(){
let current= this.head,index=0,res ="";
while(index < this.len){
res+= "-" + current.data;
current = current.next;
index++;
}
return res.slice(1)
}
toBeforeString(){
let current= this.tail,index=this.len-1,res ="";
while(index >= 0){
res+= "-" + current.data;
current = current.prev;
index--;
}
return res.slice(1)
}
}
let list = new CycleDoubleLinkList();
for (let i = 0; i < 9; i++) {
list.append(i)
}
list.remove("hello")
list.remove(0)
console.log(list.toAfterString());
console.log(list.toBeforeString());版权声明：本文为qq_52301431原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。