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

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.访问效率低