自定义链表

链表是非连续、无顺序的数据结构，链表中元素与元素之间的内存地址没有顺序关系。链表由一个个结点组成，结点中存储两类信息，第一类是存储入结点的数据，第二类是结点的指向。链表分为单项链表，双向链表，环形链表，单项链表中只有一个结点指向，指向的的下一个结点的内存地址，只能单向移动，单项操作；双向链表有两个结点指向，一个指向上一个结点的内存地址（父结点），另一个指向下一个结点的内存地址（子结点），可以双向运动，双向操作；环形链表其实是双向链表的首位结点相连。

对于链表，其好处是可以避免浪费内存空间，节省内存资源，不想数组定长会不可避免的浪费内存空间，不可以连续读取，连续操作，但是其大小可以动态改变。

 

/**
 * 双向列表结点类
 * @author lenovo
 *
 */

public class LinkNode {

	private Object obj;
	private LinkNode child;	//子类结点
	private LinkNode parent;//父类结点
	
	/**
	 * 创建有参的	构造方法
	 * @param obj
	 */
	public LinkNode(Object obj){
		this.obj=obj;
	}
	
	public LinkNode(){
		
	}

	public Object getObj() {
		return obj;
	}

	public void setObj(Object obj) {
		this.obj = obj;
	}

	public LinkNode getChild() {
		return child;
	}

	public void setChild(LinkNode child) {
		this.child = child;
	}

	public LinkNode getParent() {
		return parent;
	}

	public void setParent(LinkNode parent) {
		this.parent = parent;
	}
	
		
}

 

 

 

/**
 * 实现双向链表的方法类
 * 
 * @author lenovo
 * 
 */
public class LinkList {


	private static LinkNode head = null; // 头结点
	private LinkNode foot = head; // 尾结点

//	public static void main(String args[]) {
//
//		LinkList list = new LinkList();
//
//		list.add("新来的元素yes");
//
//		// 加入结点
//		for (int i = 0; i < 10; i++) {
//			list.add("链表元素" + i);
//		}
//
//		 list.set("XXX", 8);
//
//		 // 根据索引插入结点
//		// list.add("插入的", 8);
//		
//		 list.add("新来的元素");
//		 list.add("新来的元素2");
//
//		// 根据索引删除结点
//		 list.remove("新来的元素");
//
//		// 清空链表
//		 list.clear();
//
//		// 打印链表
//		list.printList(head);
//
//		// 得到链表的长度
//		int len = list.size();
//		System.out.println("长度：" + len);
//
//		 LinkNode temp = list.get(1); // 根据索引得到结点并打印
//		 list.printList(temp);
//
//	}

	/**
	 * 添加元素的方法
	 * 
	 * @param obj
	 *            :添加的元素
	 */
	public void add(Object obj) {

		LinkNode root = new LinkNode(obj);

		// 判断链表是否为空
		if (head == null) {
			head = root;
			foot = root;
		} else {
			foot.setChild(root);
			root.setParent(foot);

			// 为节点变为root
			foot = root;
		}

	}

	/**
	 * 插入元素的方法
	 * 
	 * @param obj
	 *            ：插入的元素
	 * @param index
	 *            ：要插入的索引
	 */
	public void add(Object obj, int index) {

		LinkNode root = new LinkNode(obj);

		if (index > size() || index < 0) {
			throw new RuntimeException("下标越界：" + index + ",size:" + size());

		} else {
			if (index == 0) { // 如果在第一个索引处插入
				head.setParent(root);
				root.setChild(head);

				head = root;

			} else if (index > 0 && index < size()) {
				int count = 0; // 计数器

				LinkNode n = head.getChild();
				while (index != count + 1) { // 得到想要插入处原来的结点
					n = n.getChild();
					count++;
				}

				LinkNode m = n.getParent();
				// 设置新的关系
				m.setChild(root);
				root.setParent(m);

				root.setChild(n);
				n.setParent(root);

			} else if (index == size()) { // 如果在结尾处插入
				add(obj);
			}
		}
	}

	/**
	 * 根据索引得到结点
	 * 
	 * @param index
	 *            ：索引
	 * @return
	 */
	public LinkNode get(int index) {
		if (index > size() || index < 0) {
			throw new RuntimeException("下标越界：" + index + ",size:" + size());

		} else {
			int count = 0; // 定义计数器

			LinkNode root = head;

			while (count != index) { // 循环得到结点
				root = root.getChild();
				count++;

			}

			return root;
		}

	}

	/**
	 * 根据索引删除结点
	 * 
	 * @param index
	 */
	public void remove(int index) {

		if (index > size() || index < 0) {

			throw new RuntimeException("下标越界：" + index + ",size:" + size());
		} else {

			// 得到指定索引的结点
			LinkNode root = this.get(index);
			// 得到结点的父结点
			LinkNode proot = root.getParent();
			// 得到结点的子结点
			LinkNode croot = root.getChild();

			if (proot == null) { // 如果是第一索引的结点
				head = croot;
			} else if (croot == null) { // 如果是最后索引的结点
				proot.setChild(null);
			} else {
				proot.setChild(croot);
				croot.setParent(proot);
			}

		}

	}

	/**
	 * 根据元素删除结点
	 * 
	 * @param obj
	 */
	public void remove(Object obj) {

		LinkNode root;

		if (head == null) {
			throw new RuntimeException("链表为空");
		}

		if (head.getObj() == obj) { // 如果是头结点
			root = head.getChild();
			root.setParent(null);
			head = root;
			return;
		} else if (foot.getObj() == obj) { // 如果是尾结点
			root = foot.getParent();
			root.setChild(null);
			foot = root;
			return;
		} else {
			root = head.getChild();
			for (int i = 0; i < size(); i++) {
				if (root.getObj() == obj) {
					remove(i + 1); // 从1的索引开始遍历
					return;
				}

				root = root.getChild();
			}
		}

	}

	/**
	 * 替换链表上相应索引结点的方法
	 * 
	 * @param obj
	 * @param index
	 */
	public void set(Object obj, int index) {

		if (index < 0 || index > size()) {
			throw new RuntimeException("下标越界：" + index + ",size:" + size());
		}

		remove(index);
		add(obj, index);

	}

	/**
	 * 统计链表长度的方法
	 * 
	 * @return
	 */
	public int size() {

		LinkNode root = new LinkNode(); // 创建一个LinkNode对象，开辟内存空间
		root = head;

		// 定义一个计数器
		int count = 0;

		while (root != null) {

			count++;
			root = root.getChild();
		}
		return count;

	}

	/**
	 * 清空链表的方法
	 */
	public void clear() {

		head.setChild(null);
		foot.setParent(null);
		head = null;
		foot = head;
	}

	/**
	 * 遍历列表
	 * 
	 * @param root
	 */
	public void printList(LinkNode root) {

		if (root != null) {

			Object obj = root.getObj();

			System.out.println(obj);

			if (root.getChild() != null) {

				printList(root.getChild()); // 递归调用
			}
		}
	}

}