链表....

数据结构中的一种常用结构.. 链表

这个怕是熟悉的不能再熟悉了,特别是用c++写过代码的选手们..

于是.今天自己实现了一些链表的操作(虽然这些操作在java里有提供方法).但是自己实现来练练手也还是不错的.

以下都是以双链表结构来实现的..

 

/**
 * 链表中的结点数据类
 * 
 * @author ds
 */
public class LinkNode {

	// 结点中的数据域
	private Object obj;
	// 结点中的指针域
	private LinkNode next;
	private LinkNode prior;

	public LinkNode(Object obj) {
		this.obj = obj;
	}

	public LinkNode getPrior() {
		return prior;
	}

	public void setPrior(LinkNode prior) {
		this.prior = prior;
	}

	public Object getObj() {
		return obj;
	}

	public void setObj(Object obj) {
		this.obj = obj;
	}

	public LinkNode getNext() {
		return next;
	}

	public void setNext(LinkNode next) {
		this.next = next;
	}

}

 

添加结点的两个方法

public void add(Object obj) {
		if (rear == null) { // 如果尾结点为空,说明链表为空,则新添加的结点就既是头结点又是尾结点
			LinkNode ln = new LinkNode(obj);
			front = ln;
			rear = ln;
		} else {// 否则接到最后
			LinkNode ln = new LinkNode(obj);
			rear.setNext(ln);
			ln.setPrior(rear);
			rear = ln;// 改变尾结点
		}
	}

public void add(int index, Object obj) {
		if (index > size() || index < 0) {
			throw new RuntimeException("输入的索引位置错误:" + index);
		} else if (index == size()) {
			add(obj);
		} else {// 索引位置正确的时候
			int i = 0;
			LinkNode ln_f = front;
			while (i < index) {
				i++;
				ln_f = ln_f.getNext();
			}
			LinkNode ln = new LinkNode(obj);
			if (i == 0) {// 加到第一个位置
				ln.setNext(ln_f);
				ln_f.setPrior(ln);
				front = ln;
			} else {
				ln.setNext(ln_f);
				ln_f.getPrior().setNext(ln);
				ln.setPrior(ln_f.getPrior());
				ln_f.setPrior(ln);
			}
		}
	}

 

清除结点的两个方法

public void removed() {
		if (rear == null) {
			System.out.println("链表中不存在结点..");
		} else if (front.equals(rear)) {// 链表中只有一个结点的时候.
			front = null;
			rear = null;
		} else {
			// 尾指针指向倒数第二个结点
			rear = rear.getPrior();
			// 丢掉最后一个结点.
			rear.setNext(null);
		}
	}

public LinkNode removed(int index) {
		if (index >= size() || index < 0) {
			throw new RuntimeException("输入的索引位置错误:" + index);
		} else {// 索引位置正确的时候
			int i = 0;
			LinkNode ln_f = front;
			while (i < index) {
				i++;
				ln_f = ln_f.getNext();
			}
			if (i == size() - 1) {// 删除的是最后一个结点的时候
				removed();
			} else if (i == 0) {// 删除的是第一个结点的时候
				front = front.getNext();
			} else {
				ln_f.getNext().setPrior(ln_f.getPrior());
				ln_f.getPrior().setNext(ln_f.getNext());
			}
			return ln_f;
		}
	}

  

得到链表的长度

	public int size() {
		// 首先长度为1
		int i = 0;
		LinkNode ln = front;
		while (ln != null) {// 当前结点的下一个结点不为空的时候.
			ln = ln.getNext();
			i++;
		}
		return i;
	}