数据结构之单向循环链接，双向循环链表的常用方法封装

单向循环链表

上一篇文章已经讲过单向链表和双向链表了，那么这里就不在赘述了，单向循环链接，双向循环链表只是加了一个从尾结点指向头结点的这一步，其他的不变

所以我们就直接封装方法啦，其他的就不在细说了

单向循环链表常用的方法

上一篇文章以及详细讲过，这里就不一一分开写了，直接合并在一起封装出来

<script>
  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 {
                let current = this.head;
                while (current.next != this.head) {
                    current = current.next;
                }
                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 || !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 < 4; i++) {
        clist.append(i)
    }
    
    console.log(clist.indexOf("hello"));
    console.log(clist.indexOf(0));
    console.log(clist.indexOf(2));
    console.log(clist.indexOf(666));

    clist.remove("hello")
    clist.remove(1)
    clist.remove(2)
    clist.remove(0)
    clist.remove(4)

    console.log(clist.toString());
</script>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

结果

移除过后就只剩下了3这个元素了

双向循环链表

<script>
   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 || !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.查找指定元素
       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))
       }

		// 6.正向字符串输出
       toAfterString(){
           let current= this.head,index=0,res ="";

           while(index < this.len){
               res+= "-" + current.data;
               current = current.next;
               index++;
           }
           return res.slice(1)
       }
		
		// 7.反向字符串输出
       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)
   }
   console.log(list);
   
   list.insert(0,"hello");
   list.insert(5,"world");
   
   list.removeAt(0);
   list.removeAt(0);
   
   console.log(list.toAfterString());
   console.log(list.toBeforeString());
</script>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

结果