数据结构与算法---链式存储结构（单向循环队列）

定义
单向循环队列是基于链表实现的但是，与链表不同的是，此单向循环队列的头尾相连，即尾指针的后继是头结点。

空表状态
此单向循环队列采用真实头结点，所以此队列为空时head,rear均指向空。

 public boolean isEmpty() {
        return size==0;
    }

1
2
3
4

添加元素
头插：
在头结点前面插入结点，即rear的后继为当前要插入的结点，当前要插入结点的后继为头结点head,添加完毕之后把head向前移动。

if(index==0){//头插
            rear.next=n;
            n.next=head;
            head=n;
        }
1
2
3
4
5

尾插：
在尾结点的后面插入结点，即尾结点的后继为此时要插入的结点，要插入结点的后继为head.然后把rear后移。

if(index==size){//尾插
            n.next=rear.next;
            rear.next=n;
            rear=n;
        }
1
2
3
4
5

一般插入：
即找到要插入位置的前一个，然后把当前位置的后继，赋给要插入结点的后继，然后当前位置的后继为当前要插入的结点。

else{
            Node p=head;
            for(int i=0;i<index-1;i++){//从真实头结点开始，把真实头结点算进去，所以经历步数为index-1次
                p=p.next;
            }
            n.next=p.next;
            p.next=n;
        }
1
2
3
4
5
6
7
8

删除元素
有效长度为1时：
即只剩一个结点时，该结点可为头结点可为尾结点，先把当前要删除的结点的数据存储一下，然后把head ,rear置空。

if(size==1){
           ret=head.data;
           head=null;
           rear=null;
        }
1
2
3
4
5

删头：
先把当前的头结点数据存储一下，然后把当前头结点的后继赋给尾结点的后继，最后把删除的头结点的数据返回。

 if(index==0){
            ret=head.data;
            rear.next=head.next;

        }
1
2
3
4
5

删尾：
先将位置移动到尾结点的前一个位置，然后把尾结点的后继赋给当前结点的后继，然后rear向前移动。

if(index==size-1){
            Node p=head;
            while (p.next!=rear){
                p=p.next;
            }
            ret=rear.data;
            p.next=rear.next;
            rear=p;
        }
1
2
3
4
5
6
7
8
9

删某一位置：
找到要删除位置的前一个位置，然后把当前位置的后一个的后一个，赋给当前位置的后继。

else{
            Node p=head;
            for(int i=0;i<index-1;i++){
                p=p.next;
            }
            Node del=p.next;
            ret=del.data;
            p.next=del.next;
        }
1
2
3
4
5
6
7
8
9

完整代码

package Ds02.动态链表;

import DS01.动态数组.List;

import java.util.Iterator;
//单向循环队列基于线性表实现的  真实头结点
//真实头结点是刚开始head和null都指null,开始存数据后就开始移动 所以空表时head=null  rear=null rear.next=head
public class LinkSingleLoop<E> implements List<E> {
    private Node head;
    private Node rear;
    private int size;
    public LinkSingleLoop(){
        head=null;
        rear=null;
        size=0;
    }
    private class Node{//内部类（结点的属性与行为）
        E data;//数据域
        Node next;//指针域，因为存下一个节点，节点类型为Node
        Node(){
            this(null,null);
        }
        Node(E data, Node next){
            this.data=data;
            this.next=next;
        }
        @Override
        public String toString(){
            return data.toString();
        }
    }
    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void add(int index, E e) {
        if(index<0&&index>size){
            throw new IllegalArgumentException("角标越界");
        }
        Node n=new Node();
        n.data=e;
        if(isEmpty()){//为表时head=null  rear=null    此时为真实头结点
            head=n;
            rear=n;
            rear.next=head;
        }
        if(index==0){//头插
            rear.next=n;
            n.next=head;
            head=n;
        }else if(index==size){//尾插
            n.next=rear.next;
            rear.next=n;
            rear=n;
        }else{
            Node p=head;
            for(int i=0;i<index-1;i++){//从真实头结点开始，把真实头结点算进去
                p=p.next;
            }
            n.next=p.next;
            p.next=n;
        }
        size++;
    }

    @Override
    public void addFirst(E e) {
        add(0,e);
    }

    @Override
    public void addLast(E e) {
        add(size-1,e);
    }

    @Override
    public E get(int index) {
        if(isEmpty()){
            throw new IllegalArgumentException("链表为空");
        }
        if(index<0||index>=size){
            throw new  IllegalArgumentException("角标越界");
        }
        Node p=head;
        for(int i=0;i<index;i++){
            p=p.next;
        }
        return p.data;
    }

    @Override
    public E getFirst() {
        return get(0);
    }

    @Override
    public E getLast() {
        return get(size-1);
    }

    @Override
    public void set(int index, E e) {
        if(isEmpty()){
            throw new IllegalArgumentException("表为空");
        }
        if(index<0||index>=size){
            throw new IllegalArgumentException("角标越界");
        }
        Node p=head;
        for(int i=0;i<index;i++){
            p=p.next;
        }
        p.data=e;
    }

    @Override
    public boolean contains(E e) {
        return find(e)!=-1;
    }

    @Override
    public int find(E e) {
        Node p=head;
       for(int i=0;i<size;i++){
           if(p.data.equals(e)){
               return i;
           }
       }
        return -1;
    }

    @Override
    public E remove(int index) {
        if(isEmpty()){
            throw new IllegalArgumentException("表为空");
        }
        if(index<0&&index>=size){
            throw new IllegalArgumentException("角标越界");
        }
        E ret=null;
        if(size==1){
           ret=head.data;
           head=null;
           rear=null;
        }else if(index==size-1){
            Node p=head;
            while (p.next!=rear){
                p=p.next;
            }
            ret=rear.data;
            p.next=rear.next;
            rear=p;
        }else if(index==0){
            ret=head.data;
            rear.next=head.next;

        }else{
            Node p=head;
            for(int i=0;i<index-1;i++){
                p=p.next;
            }
            Node del=p.next;
            ret=del.data;
            p.next=del.next;
        }
        size--;
        return ret;
    }

    @Override
    public E removeFirst() {
        return remove(0);
    }

    @Override
    public E removeLast() {
        return remove(size-1);
    }

    @Override
    public void removeElement(E e) {
        int index=find(e);
        if(index!=-1){
            remove(index);
        }else{
            throw new IllegalArgumentException("元素不存在");
        }
    }

    @Override
    public void clear() {
        head=null;
        rear=null;
        size=0;
    }

    @Override
    public int getCapacity() {
        return 0;
    }

    @Override
    public Iterator<E> iterator() {
        return new LinkSingleLoopIterator();
    }
    public class LinkSingleLoopIterator implements Iterator<E>{
        Node p;
        public LinkSingleLoopIterator(){
            p=new Node();
            p.next=head;
        }

        @Override
        public boolean hasNext() {
            return p!=rear;
        }

        @Override
        public E next() {
            p=p.next;
            return p.data;
        }
    }
}

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232