Netjava Lesson11 离散的存储空间——链表

2013.07.30

 

上课内容：链表

 

上节课我们学习了队列，我们知道队列也是由数组来实现的，而数组的新建所要开辟的内存空间是连续的。
而我们这节课要讲的链表是在内存中开辟不连续的空间，每一个节点可以存储不同的数据类型。
链表存储没有顺序，它是由节点组成的，除了根节点和尾节点，每一个节点跟两个节点相连，下面我们来介绍三中链表：

 

单链表：一个节点由两部分组成：
一个是该节点的数据，这里用data表示。
一个是该节点指向的地址，这里用next表示。
我们从一个根节点开始，给根节点一个data，当我们再建立一个节点时，会把地址给根节点的next，这样，我们再创建一个地址，就会把地址给上一个节点的next，从而达到了连接的效果。
链表的好处就是每新建一个节点时，就会新开辟一段内存空间，删除节点时，就会自动释放，这样能够大大地节省内存空间。

 

双链表：一个节点由三部分组成：
一个是该节点的数据，用data表示。
一个是该节点指向的地址，用next表示。
一个是指向该节点的地址，用previous表示。
双链表比单链表多了一个指向该节点的地址，这里在做一些东西时也可以大大地提升效率。
比如我们浏览器的按钮，包括前进和后退键，但如果我们只有后面的地址，就要从新开始遍历，会大大地增加时间。

 

双向循环链表：一个节点同样由三部分组成，与双链表相同。
循环链表是双链表的一个补充，是将双链表首尾想接，就是指向root节点的地址储存在尾节点last。
这样首尾相连围起来就像一个圆圈，从其中任意一个节点访问，都可以访问next和previous节点，没有了双链表的边界条件的问题。

今天我们要实现的是双链表：

首先我们定义一个接口：

public interface NodeLinkedListInterface {

	/**
	 * 添加节点的方法
	 * 
	 * @param node新添加的节点对象
	 */
	public abstract void add(Node node);

	/**
	 * 在指定索引位置添加新节点
	 * 
	 * @param node要添加的新节点
	 * @param index指定的索引位置
	 */
	public abstract void add(Node node, int index);

	/**
	 * 移除指定的节点
	 * 
	 * @param node要被移除的节点对象
	 * @return 返回true和false，true表示移除成功，false表示移除失败
	 */
	public abstract boolean remove(Node node);

	/**
	 * 移除指定所以位置的节点
	 * 
	 * @param index指定要移除的节点索引
	 * @return 返回true和false，true表示移除成功，false表示移除失败
	 */
	public abstract boolean remove(int index);

	/**
	 * 获取指定索引位置的节点对象
	 * 
	 * @param index指定的索引位置
	 * @return 返回节点对象，如果index的范围超出size，则返回null.
	 */
	public abstract Node get(int index);

	/**
	 * 获取双链表中存储的元素总数
	 * 
	 * @return 返回size的值，如果为0则表示链表中没有节点
	 */
	public abstract int size();

}

 

然后我们定义节点类：

public class Node {
	//节点的数据
	private Object data;
	//节点的下一个节点
	private Node next;
	//节点的上一个节点
	private Node previous;

	//构造方法
	public Node(Object data) {
		this.data = data;
	}

	//构造方法
	public Node(Object data, Node next, Node previous) {
		this.data = data;
		this.next = next;
		this.previous = previous;
	}

	public Object getData() {
		return data;
	}

	public void setData(Object data) {
		this.data = data;
	}

	public Node getNext() {
		return next;
	}

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

	public Node getPrevious() {
		return previous;
	}

	public void setPrevious(Node previous) {
		this.previous = previous;
	}

}

 

最后我们定义链表类来实现这个接口：

public class NodeLinkedList implements NodeLinkedListInterface {

	private int size = 0;
	private Node root = null;
	private Node last = null;

	/**
	 * 添加节点的方法
	 * 
	 * @param node新添加的节点对象
	 */
	public void add(Node node) {
		//如果没有节点，将node给根节点
		if (root == null) {
			root = node;
		} else {
			//将最后的一个节点的下一个节点设置为node
			last.setNext(node);
			//node为last的上一个节点
			node.setPrevious(last);
		}
		//将node设置为尾节点
		last = node;
		//链表长度加一
		size++;
	}

	/**
	 * 在指定索引位置添加新节点
	 * 
	 * @param node要添加的新节点
	 * @param index指定的索引位置
	 */
	public void add(Node node, int index) {
		//设置临时节点temp为根节点
		Node temp = root;
		//从根节点开始遍历找到第i个节点
		for (int i = 0; i < index; i++) {
			temp = temp.getNext();
		}
		//如果i不在边界
		if (index < size - 1 && index > 0) {
			//将node插入其中，与前后的地址结合起来
			temp.getPrevious().setNext(node);
			node.setPrevious(temp.getPrevious());
			temp.setPrevious(node);
			node.setNext(temp);
			//链表长度加一
			size++;
		} else if (index == 0) {
			//如果插在队开头，将node设置为根节点
			root.setPrevious(node);
			node.setNext(root);
			root = node;
			//链表长度加一
			size++;
		} else {
			//将节点添加至末尾
			this.add(node);
		}
	}

	/**
	 * 移除指定的节点
	 * 
	 * @param node要被移除的节点对象
	 * @return 返回true和false，true表示移除成功，false表示移除失败
	 */
	public boolean remove(Node node) {
		//建立临时节点temp为根节点
		Node temp = root;
		for (int i = 0; i < size; i++) {
			//循环找出第i个节点
			temp = temp.getNext();
			//判断第i个节点和node是否相同
			if (temp == node) {
				//如果相同，让temp两端的节点首尾相接
				temp.getNext().setPrevious(temp.getPrevious());
				temp.getPrevious().setNext(temp.getNext());
				//链表长度减一
				size--;
				//返回真
				return true;
			}
		}
		//否则返回否
		return false;
	}

	/**
	 * 移除指定所以位置的节点
	 * 
	 * @param index指定要移除的节点索引
	 * @return 返回true和false，true表示移除成功，false表示移除失败
	 */
	public boolean remove(int index) {
		//如果给的i不在链表长度范围内
		if (index < 0 || index >= size) {
			//返回否
			return false;
		}else if(index ==0){
			//如果在开头，就让第二个节点为根节点
			root = root.getNext();
			root.setPrevious(null);
			//链表长度减一
			size--;
			//返回真
			return true;
		}
		//设置临时节点node为根节点
		Node node = root;
		//通过循环找到第index个节点
		for (int i = 0; i < index; i++) {
			node = node.getNext();
		}
		//移除这个节点
		this.remove(node);
		//返回真
		return true;
	}

	/**
	 * 获取指定索引位置的节点对象
	 * 
	 * @param index指定的索引位置
	 * @return 返回节点对象，如果index的范围超出size，则返回null.
	 */
	public Node get(int index) {
		//如果index超出范围，就返回null
		if (index < 0 || index >= size) {
			return null;
		}
		//设置node为根节点
		Node node = root;
		//循环找到第index个节点
		for (int i = 0; i < index; i++) {
			node = node.getNext();
		}
		//返回node
		return node;
	}

	/**
	 * 获取双链表中存储的元素总数
	 * 
	 * @return 返回size的值，如果为0则表示链表中没有节点
	 */
	public int size() {
		return size;
	}

}

 

对于实现接口的双链表类，我想我的代码还不是很精简，所以欢迎大家提意见，我一定虚心接受~