链表总结_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 链表总结

链表总结

 2013/8/4 4:08:28  王浩洋  程序员俱乐部  我要评论(0)
  • 摘要:1.什么是链表链表是一种物理储存单元上非连续,非顺序的储存结构,链表由一系列节点组成,节点可以在运行时动态生成。每个节点包括两个部分:一个是储存元素数据的数据域,另一个是储存下一个节点地址的指针域。2.链表的构建下面以一个双向链表为例构建链表首先定义一个链表接口,代码如下:publicinterfaceNodeLinkedListInterface{/***添加节点的方法**@paramnode新添加的节点对象*/publicabstractvoidadd(Nodenode)
  • 标签:总结
1.什么是链表
    链表是一种物理储存单元上非连续,非顺序的储存结构,链表由一系列节点组成,节点可以在运行
时动态生成。每个节点包括两个部分:一个是储存元素数据的数据域,另一个是储存下一个节点地址的指针域。
2.链表的构建
下面以一个双向链表为例构建链表
首先定义一个链表接口,代码如下:
class="java">
public interface NodeLinkedListInterface {
	/**
	 * 添加节点的方法
	 * 
	 * @param node新添加的节点对象
	 */
	public abstract void add(Node node);

	/**
	 * 在指定索引位置添加新节点
	 * 
	 * @param node要添加的新节点
	 * @param index指定的索引位置
	 */
	public abstract void add(Node node, int index);
	/**
	 * 让指定位置的节点互相交换位置
	 * @param index1,index2指定的节点位置
	 */
	public abstract void exchange(int index1,int index2);

	/**
	 * 移除指定的节点
	 * 
	 * @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 obj;
	private Node next;
	private Node previous;
	public Node(Object obj){
		this.obj=obj;
	}
	public Node(Object obj, Node next, Node previous) {
		super();
		this.obj = obj;
		this.next = next;
		this.previous = previous;
	}
	public Object getObj() {
		return obj;
	}
	public void setObj(Object obj) {
		this.obj = obj;
	}
	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 LinkedList implements NodeLinkedListInterface {
	private int size;
	private Node root = null;
	private Node last = null;

	public LinkedList() {
		this.size = 0;
	}

	/**
	 * 链表构造方法
	 * 
	 * @param size
	 * @param root
	 * @param last
	 */
	public LinkedList(int size, Node root, Node last) {
		super();
		this.size = size;
		this.root = root;
		this.last = last;
	}

	public void add(Node node) {

		size++;
		if (root == null) {
			root = node;
			root.setPrevious(null);
			last = root;

		} else {
			last.setNext(node);
			node.setPrevious(last);
			node.setNext(null);
			last = node;

	}

	public void add(Node node, int index) {
		if (index < 0 || index > size) {
			System.out.println("没有该位置");
		} else if (index == 0) {
			Node cnode = root;
			root = node;
			node.setNext(cnode);
			cnode.setPrevious(node);
		} else {
			Node newnode = this.get(index);
			// 获取父节点
			Node fnode = newnode.getPrevious();
			// 使父节点指向要添加的节点
			fnode.setNext(node);
			node.setPrevious(fnode);
			node.setNext(newnode);
			newnode.setPrevious(node);
		}
		size++;
	}

	public boolean remove(Node node) {
		Node newnode = root;
		for (int i = 0; i < size; i++) {
			if (newnode == node) {
				// 获取要移除的节点的父节点和子节点,使其相连
				Node fnode = newnode.getPrevious();
				Node cnode = newnode.getNext();
				if (fnode == root) {
					root = root.getNext();
				} else if (cnode == last) {
					last = last.getPrevious();
				} else {
					fnode.setNext(cnode);
					cnode.setPrevious(fnode);
					newnode = null;
				}
				break;
			} else {
				newnode = newnode.getNext();
			}

		}
		size--;
		return false;
	}

	public boolean remove(int index) {
		if (index < 0 || index > size) {
			System.out.println("没有该位置");
		} else {
			Node node = this.get(index);
			// 获取要移除的节点的父节点和子节点,使其相连
			Node fnode = node.getPrevious();
			Node cnode = node.getNext();
			if (fnode == null) {
				root = root.getNext();
			} else if (cnode == null) {
				last = last.getPrevious();
			} else {
				fnode.setNext(cnode);
				cnode.setPrevious(fnode);
				node = null;
			}
		}
		size--;
		return false;
	}

	public Node get(int index) {
		if (index < 0 || index > size) {
			System.out.println("要返回的结果不存在");
			return null;
		}
		Node node = root;
		for (int i = 0; i < index; i++) {
			node = node.getNext();
		}
		return node;
	}

	public int size() {
		return size;
	}
}


3.链表的优缺点
优点:1.方便添加和删除
       2.长度可以变
缺点:1.访问效率低
发表评论
用户名: 匿名