数据结构_链表实现无限循环的"环"结构/循环队列

       简单的数据结构应用,使用链表实现了"环"结构,代码如下:

package com.wly.algorithmbase.datastructure;

/**
 * 链表实现无限循环的"环",结构从左(head)到右(tail)
 * @author wly
 * @param <E>实体类
 */
class ChainCycle<E> {
	
	private Node<E> head; //头节点
	private Node<E> tail; //尾节点
	
	private Node<E> current; //当前遍历节点
	
	private int mSize = 0; //尺寸
	
	
	public static void main(String[] args) {
		ChainCycle<Student> chain = new ChainCycle<Student>();
		chain.insert(new Node<Student>(new Student("A",1)));
		chain.insert(new Node<Student>(new Student("B",2)));
		chain.insert(new Node<Student>(new Student("C",3)));

		System.out.println("向右遍历:");
		for(int i=0;i<6;i++) {
			Student s = chain.next();
			System.out.println(s.name + "_" + s.age);
		}
		System.out.println("向左遍历:");
		for(int i=0;i<6;i++) {
			Student s = chain.prev();
			System.out.println(s.name + "_" + s.age);
		}
		System.out.println("删除元素,并向右遍历:");
		chain.remove();
		for(int i=0;i<6;i++) {
			Student s = chain.prev();
			System.out.println(s.name + "_" + s.age);
		}

	}
	
	public E next() {
		if(current == null) {
			current = head;
		} else {
			current = current.right;
		}
		
		if(current != null) {
			return current.e;
		} else {
			return null;
		}
	}
	
	
	public E prev() {
		if(current == null) {
			current = head;
		} else {
			current = current.left;
		}
		
		if(current != null) {
			return current.e;
		} else {
			return null;
		}
	}
	
	/**
	 * 插入节点到尾节点
	 * @param node
	 */
	public void insert(Node<E> node) {
		if(tail == null) {
			head = node;
			tail = head;
			head.right = tail;
			head.left = tail;
			tail.right = head;
			tail.left = head;
		} else {
			head.left = node;
			tail.right = node;
			node.left = tail;
			node.right = head;
			tail = node;
			head.left = tail;
		}

		mSize ++;
	}
	
	/**
	 * 移除尾节点
	 */
	public void remove() {
		
		if(mSize == 0) {
			System.out.println("当前列表为空,无法再行移除元素!");
			return ;
		} else if(mSize == 1) {
			tail = null;
			head = null;
		} else {
			//连接新的tail和head
			head.left = tail.left;
			tail.left.right = head;
			tail = tail.left;
		}
	}
	
	public int size() {
		return mSize;
	}
}

/**
 * 节点类,封装了实体类E
 * @param <E> 
 */
class Node<E> {
	Node left;
	Node right;
	E e; //实体类
	public Node(E e) {
		this.e = e;
	}
}

/**
 * 测试实体类
 */
class Student {
	String name;
	int age;
	
	public Student(String name,int age) {
		this.age = age;
		this.name = name;
	}
}
       运行结果:
向右遍历:
A_1
B_2
C_3
A_1
B_2
C_3
向左遍历:
B_2
A_1
C_3
B_2
A_1
C_3
删除元素,并向右遍历:
B_2
A_1
B_2
A_1
B_2
A_1

       O啦~~~

       转载请保留出处:http://www.voidcn.com/article/p-awggfsxs-bha.html

       谢谢!!

相关文章
相关标签/搜索