java链表

链表，可以把它想象为车的链子，一环扣一环，上一个指向下一个。与队列相同，链表克服了数组需要预先知道数据长度的缺点，但失去了数组随机存取的优点。另外，链表的结构使其能充分利用计算机的内存空间，灵活的利用内存。但缺点在于其增加了引用域，使空间开销较大。

链表：由一连串节点组成，每个节点包含数据域和引用域。链表分为单链表，双链表和循环链表。

java中的链表类似于c中的链表，只是c中通过指针把相邻的节点联系起来，前一个节点通过指针来保存下一个节点的地址，所以得到链表的根节点，就能得到链表的所以元素。java中没有指针，在java中通过引用实现指针的功能，java中节点保存了下一个节点对象的引用，就可得到其下一个节点对象。

先写个单链表，

首先，我们要定义一个节点（Node）类：

 

package cn.lzj0726;

/**
 * 节点类
 * 
 * @author lzj
 * 
 */
public class Node {
	private Object obj;// 数据
	private Node next;// 引用，指向下一个节点

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

}

 

链表类：

package cn.lzj0726;

/**
 * 单链表类
 * 
 * @author lzj
 * 
 */
public class LinkedList {
	private Node root;// 声明一个根节点
	private Node endNode;// 声明一个尾节点
	private int size;// 声明链表节点的个数

	/**
	 * 添加节点的方法
	 * @param node要被添加的的节点对象时
	 */
	public void add(Node node) {
		if (root == null) {
			root = node;// 把新节点给根节点
			endNode = node;// 把新节点给尾节点
		} else {// 将新节点添加到尾节点之后
			endNode.setNext(node);// 把新节点设置为尾节点的下一个节点
			endNode = node;// 将尾节点移动到新添加的节点上
		}
		size++;// 计数器加一
		// System.out.println(size + ">>>>>>>>>>>>>>>>>>");

	}

	/**
	 * 通过索引得到节点的方法
	 * 
	 * @param index索引
	 * @return 返回节点的数据
	 */
	public Object get(int index) {
		if (index < 0 || index >= size)// 如果索引小于0或大于等于index
			return null;
		Node node = root;// 根节点
		for (int i = 0; i < index; i++) {
			node = node.getNext();// 循环得到索引指向的节点
		}
		return node.getObj();// 返回索引指向的节点的数据
	}

	/**
	 * 通过索引移除节点的方法
	 * 
	 * @param index索引
	 * @return 返回所移除的的节点的数据
	 */
	public Object remove(int index) {
		Node node = root;// 把根节点赋予node
		Node removeNode = node;// 要删除的节点初始化为root节点
		if (index == 0) {// 若要删除的是根节点
			root = node.getNext();// 把下一个节点设为root根节点
			removeNode = root;// 把根节点存到removeNode
		} else {
			for (int i = 0; i < index - 1; i++) {
				node = node.getNext();// 得到索引指向的节点的上一个节点，赋予node
			}
			if (index == size - 1) {// 若指向最后一个节点
				removeNode = node.getNext();// 把该节点赋予removeNode
				node.setNext(null);// 把最后一个节点的引用设为null
			} else {
				removeNode = node.getNext();// 把索引所指向的节点的引用赋予removeNode
				Node nextNode = removeNode.getNext();// 把索引所指向的节点的下一个节点的引用赋予nextNode
				node.setNext(nextNode);// 把索引所指向的节点的引用设置为nextNode
			}

		}
		size--;
		return removeNode.getObj();
	}

	/**
	 * 得到节点数的方法
	 * 
	 * @return 返回节点数
	 */
	public int getSize() {
		return size;
	}

}

 

测试链表：

package cn.lzj0726;

public class LinkedTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		 LinkedList linked = new LinkedList();
		 // 实例化一个随机类对象
		 java.util.Random rand = new java.util.Random();
		 for(int i = 0;i<10;i++){
		 Node node = new Node();
		 node.setObj(rand.nextInt(100));
		 linked.add(node);
		 }
		 for(int i = 0;i<linked.getSize();i++){
		 System.out.println(linked.get(i));
		 }
		 System.out.println(">>>>>>>>>>>>>>>>>>>>>"+linked.getSize());
		 linked.remove(3);
		 for(int i = 0;i<linked.getSize();i++){
		 System.out.println(linked.get(i));
		 }

		BothLinkedList link = new BothLinkedList();
		for (int i = 0; i < 10; i++) {
			Node node = new Node();
			node.setObj(rand.nextInt(100));
			link.add(node);
		}
		for (int i = 0; i < link.getSize(); i++) {
			System.out.println(link.get(i).getObj());
		}
		System.out.println(">>>>>>>>>>>>>>>>>>>>>" + linked.getSize());
		linked.remove(3);
		for (int i = 0; i < linked.getSize(); i++) {
			System.out.println(link.get(i).getObj());
		}
		System.out.println(">>>>>>>>>----->>>>>>>>>>>>");
		sort(link);
		for (int i = 0; i < linked.getSize(); i++) {
			System.out.println(link.get(i).getObj());
		}
	}

	// 选择排序
	public static void sort(BothLinkedList link) {
		for (int i = 0; i < link.getSize(); i++) {
			int minIndex = i;
			// 找出值最小的一个索引
			for (int j = i + 1; j < link.getSize(); j++) {
				if ((int) link.get(j).getObj() < (int) link.get(minIndex)
						.getObj()) {
					minIndex = j;
				}
			}
			// 交换	
			Object temp = null;//声明Object类型的temp变量
			temp = link.get(i).getObj();//把下标为i的节点的值存在temp中
			link.get(i).setObj(link.get(minIndex).getObj());//把下标为i的值设置为下标为minIndex的节点的值
			link.get(minIndex).setObj(temp);//把下标为minIndex的值设为temp
		}
	}
}

 

经测试，单链表可以用