疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

Java实现循环链表


 

 
在单链表中,如果把终端节点的引用指向头结点,就使整个链表形成以个环。这种链表称为循环链表。
 
链表中的节点代码:
 
public class Node <T>{
private T data; //数据
private Node<T> next; //下一个节点的引用
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
 
链表源代码:
/**
 * 循环链表
 * @author Administrator
 *
 */
public class CircularLinkedList <T>{
private Node<T> head; //头指针
@SuppressWarnings("unused")
private Node<T> rear; //尾指针
/**
* 构造空循环链表
*/
public CircularLinkedList(){
head = new Node<T>();
head.setNext(head);
}
/**
* 初始化循环链表(尾插法)
* @param e 初始数据
* @param n 大小
*/
public CircularLinkedList(T[] e,int n){
head = new Node<T>();
Node<T> s = head; //工作指针
Node<T> s2 = null;
for (T t : e) {
s2 = new Node <T>();
s2.setData(t);
s.setNext(s2);
s = s2;
}
s.setNext(head); //尾节点指向头指针,形成环
if(n != 0)
rear = s;  //把尾节点引用赋值给尾指针(方便以后找到尾节点)
}
/**
* 插入元素
* @param e 插入的元素
* @param index 插入的位置
* @return
*/
public boolean insert(T e,int index){
if(index < 1 || index > size()+1)
throw new ArrayIndexOutOfBoundsException();
Node<T> s = head;
Node<T> s2= null;
int count = 0;
   
while(count < index - 1){
s = s.getNext();
count ++;
}
s2 = new Node<T>();
s2.setData(e);
s2.setNext(s.getNext());
s.setNext(s2);
if(index == size()+1) //判断插入位置为最后
rear = s2; //将新尾节点的引用赋值给尾指针
return true;
}
/**
* 按位置删除元素
* @param index 位置
* @return
*/
public boolean remove(int index){
if(index < 1 || index > size())
throw new ArrayIndexOutOfBoundsException();
int count = 0; //计数器
Node<T> s = head;
while(count < index -1){
s = s.getNext();
count ++;
}
s.setNext(s.getNext().getNext());
if(index == size()&&size()!=1)
rear = s;
return true;
}
/**
* 给定元素删除
* @param e
* @param index
* @return
*/
public boolean remove(T e,int index){
if(index < 0 || index > size())
throw new ArrayIndexOutOfBoundsException();
int count = 0;
Node<T> s = head;
while(count < index - 1){
s = s.getNext();
count ++;
}
s.setNext(s.getNext().getNext());
//是否删除的是最后一个元素
if(index == size()&&index!=1){
rear = s;
}
return true;
}
/**
* 返回元素在链表中的位置
* @param e
* @return
*/
public List<Integer> locate(T e){
List<Integer> list = new ArrayList<Integer>();
Node<T> s = head;
int count = 0; //计数器
while(!s.getNext().equals(head)){
count ++;
s = s.getNext();
if(s.getData().equals(e))
list.add(count);
}
  return list;
}
/**
* 按位置查询元素
* @param index
* @return
*/
public T get(int index){
if(index < 1 || index > size())
throw new ArrayIndexOutOfBoundsException();
int count = 0;
Node<T> s = head;
while(count < index){
s = s.getNext();
count ++;
}
return s.getData();
}
/**
* 替换元素
* @param index
* @param e
* @return
*/
public boolean replace(int index,T e){
if(index < 1 || index > size())
throw new ArrayIndexOutOfBoundsException();
Node<T> s = head;
int count =0;
while(count < index){
s= s.getNext();
count ++;
}
s.setData(e);
return true;
}
/**
* 判断链表是否为空
* @return
*/
public boolean isEmpty(){
if(head.getNext().equals(head))
return true;
return false;
}
/**
* 获取链表的长度
* @return
*/
public int size(){
Node<T> s = head;
int size = 0;
while(true){
s = s.getNext();
if(s.equals(head))
break;
else
size++;
}
return size;
}
@Override
public String toString(){
String str = "[";
Node<T> s= head;
while(!s.getNext().equals(head)){
s = s.getNext();
if(s.getNext().equals(head))
str = str + s.getData();
else
str = str + s.getData() + ",";
}
str = str + "]";
return str;
}
}
 
在代码中定义尾指针rear的目的是为运算方便。
 
如:在很多实际问题中要找到终端节点, 在有尾指针的情况下时间复杂度为O(1),若没有就要从头指针一直遍历整个链表时间复杂度为O(n)