`
felixour
  • 浏览: 31495 次
  • 性别: Icon_minigender_1
  • 来自: 湖南
社区版块
存档分类
最新评论

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;
	}

}

 

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

0
2
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics