链表的使用

    数据存储共有两种形式，一种是连续的，比如说数组，存储时是连续的；还有一种是离散的，这就是链表。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的引用域。 链表又分为单链表，双链表和循环链表。

我们先来看单链表，图示为：

 

 

 

由图我们可以看出结点左端的方格是数据域，用来存储数据，而右端是引用域，用来存储下一个节点的地址，便于我们方便的读取到。单链表的引用域是单一指向的，指向他的下一个结点。第一个结点称之为根节点，最后一个节点称之为尾结点。

循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的尾结点的引用域是指向该循环链表的根节点，从而构成一个环形的链。

而双链表就比单链表方便很多，因为单链表指向是单向的，而双链表有两个引用域，一个指向前一个结点，另一个指向下一个结点。当然根节点只有指向下一个节点的引用域，而尾结点只有指向前一个的引用域。这样的话查找数据时就有两种方法，一种是从前面开始查找，一种就是从后面开始查找。

 

 

下面附上我写的双链表的代码：

结点类：

 

public class Node {

	private Object obj;// 数据域

	private Node next;// 引用域
	private Node prior;//引用域

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

	public Node getPrior() {
		return prior;
	}

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

	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 class LinkedList {

	public Node root;// 根节点
	public Node endNode;// 尾节点
	private int size;// 链表大小

	/**
	 * method of add node
	 * 
	 * @param node
	 */
	public void add(Node node) {

		if (size == 0) {
			root = node;
			endNode = node;

		} else {
			endNode.setNext(node);
			node.setPrior(endNode);
			endNode = node;
		}

		size++;
	}

	/**
	 * method of remove node
	 * 
	 * @param node
	 */
	public Object removeNode(int index) {
		Node node = root;
		Node removeNode;

		if (index == 0) {
			removeNode = root;
			root = node.getNext();

		} else {
			for (int i = 0; i < index - 1; i++) {
				node = node.getNext();
			}
			if (index == size - 1) {
				removeNode = node.getNext();
				node.setNext(null);
			} else {
				removeNode = node.getNext();
				Node nextNode = removeNode.getNext();
				node.setNext(nextNode);
				nextNode.setPrior(node);
			}

		}
		size--;
		return removeNode;
	}

	/**
	 * 按正序查找指定索引位置的值
	 * 
	 * @param index
	 * @return
	 */
	public Object get(int index) {

		if (index < 0 || index >= size) {
			return null;
		} else {

			Node node = root;

			for (int i = 0; i < index; i++) {
				node = node.getNext();

			}

			return node.getObj();
		}

	}

	/**
	 * 按倒序查找指定索引位置的值
	 * 
	 * @param index
	 * @return
	 */
	public Object getReverse(int index) {

		if (index < 0 || index >= size) {
			return null;
		} else {

			Node node = endNode;

			for (int i = size - 1; i > index; i--) {
				node = node.getPrior();
			}
			return node.getObj();
		}
	}

	/**
	 * 返回链表大小的方法
	 * 
	 * @return
	 */
	public int size() {
		return size;
	}

	/**
	 * 得到指定索引位置节点的方法
	 * 
	 * @param index
	 * @return
	 */
	public Node getNode(int index) {
		if (index < 0 || index >= size) {
			return null;
		} else {
			Node node = root;
			for (int i = 0; i < index; i++) {
				node = node.getNext();
			}
			return node;
		}
	}
}

 

 当然，链表的排序也和数组不一样，链表排序时只需改变引用域的指向，但是涉及根节点和尾结点时，要变更根结点和尾结点（将新结点设置为根结点或尾结点）。下面附上双链表的直接插入排序：

 

 

 

 

/**
 * 创建InsertSort类   内置直接插入排链表顺序的方法  按正序排列
 * @author Administrator
 *
 */
public class InsertSort  {

	/**
	 * 对链表排序的方法   直接插入排序
	 * @param list
	 */
	public void InsertSort(LinkedList list) {
		int i, j;
		for (i = 0; i < list.size(); i++) {
			Node temp = list.getNode(i);
			
			for (j = i; j > 0   
					&& Double.parseDouble(temp.getObj().toString()) < Double//将链表节点所存的object型数据转换为double型 便于比较
							.parseDouble(list.getNode(j - 1).getObj()
									.toString()); j--) {
				if (j == 1) {//排前两个的顺序 
					             //当根节点数据大于它下一个节点的的数据的时候 
					             //改变这两个节点的指针指向 并将第二个节点设置为根节点
					Node node1 = list.getNode(j - 1);
					Node node2 = node1.getNext();
					Node node3 = node2.getNext();

					node2.setNext(node1);
					node1.setPrior(node2);
					node1.setNext(node3);
					node3.setPrior(node1);

					list.root = node2;
				} else if (j == list.size() - 1) {//排序最后两个节点数据  同样是改变指针指向
					Node node1 = list.getNode(j - 1);
					Node node2 = node1.getNext();
					Node node3 = node1.getPrior();

					node3.setNext(node2);
					node2.setPrior(node3);
					node2.setNext(node1);
					node1.setPrior(node2);

					list.endNode = node1;

				} else {//排序中间节点数据的方法 改变节点指针指向即可
					Node node1 = list.getNode(j - 1);
					Node node2 = node1.getNext();
					Node node3 = node2.getNext();
					Node node4 = node1.getPrior();

					node4.setNext(node2);
					node2.setPrior(node4);
					node2.setNext(node1);
					node1.setPrior(node2);
					node1.setNext(node3);
					node3.setPrior(node1);
				}
			}

		}

	}

}

 

 

 

备注：图片来自于360百科