链表总结

 

首先，链表是一种顺序存储结构，每一个节点由存储数据元素的数据域和指向下一个节点的指针域（双向链表还有指向父节点的指针域）组成。链表在内存中是非连续、非顺序。与线性表相比，链表的插入和删除比较方便。

一、单向链表

单向链表的节点由存储数据的数据域和指向下一个节点的指针域组成，在java中我们用类封装其数据结构，代码示例：

public class LinkNode {

			private LinkNode child;// 对下一个节点的应用
			private LinkNode parent;// 对上一个节点的应用
			private Object obj;// 节点内的数据对象
			private LinkNode next;// 节点的下个元素
			private String name;
			// 在创建节点对象的时候就传入节点中的数据对象
			public LinkNode(Object obj) {
				this.obj = obj;
			}

			public Object getObj() {
				return obj;
			}

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

			public LinkNode getNext() {
				return next;
			}

			public void setNext(LinkNode next) {
				this.next = next;
			}

			public LinkNode getChild() {
				return child;
			}

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

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

			public LinkNode getParent() {
				return parent;
			}
	
			public void setName(String name){
				this.name= name;
			}
	
			public String getName(){
				return name;
			}

		}

 

有了这个类我们就可以实现一个简单的单向链表。

private LinkNode root;

		public class LinkList(){
			// 主函数
			public static void main(String[] args) {
			LinkList list = new LinkList();
			//创建链表
			LinkNode root = list.creatLink();
			//遍历
			list.printLinkList(root);
			}
	
			/**
			* 创建链表
			*
			* @return
			*/
			public LinkNode creatLink() {
			String s = "根节点";
			root = new LinkNode(s);
			LinkNode n1 = new LinkNode("一节点");
			LinkNode n2 = new LinkNode("二节点");
			LinkNode n3 = new LinkNode("三节点");
			LinkNode n4 = new LinkNode("四节点");
			root.setNext(n1);
			n1.setNext(n2);
			n2.setNext(n3);
			n3.setNext(n4);
			return root;
			}
	
			/**
			* 遍历链表的方法
			*
			* @param root
			*/
			public void printLinkList(LinkNode root) {
			if (null != root) {
				Object data = root.getObj();
				System.out.println(data);
				LinkNode temp = root.getNext();
				printLinkList(temp);
				}
	
			}	
		}

 

这样我们就实现了一个简单的单向链表

二、双向链表

双向链表实际上是单向链表的改进，加上了一个指向父节点的指针域，在封装双向节点的结时，大致和单向链表相同，只要加上父节点。例如我们实现一个用链表实现存储工人工资，并按顺序输出

/**

	 *	加入新的节点
	 * 
	 * @param obj
	 */
	public void add(Object obj) {
		// 创建新的节点
		LinkNode node = new LinkNode(obj);
		// 判断链表是够空
		if (null == front) {
			front = node;
			last = front;
		} else {
			last.setChild(node);
			node.setParent(last);
			last = node;
		}

	}

	/**
	 * 在指定索引插入节点
	 * 
	 * @param index
	 * @param obj
	 */
	public void insertIndexObj(int index, Object obj) {
		if (this.getLength() < index || index < 0) {
			throw new java.lang.RuntimeException("下标越界" + index + ",size:"
					+ this.getLength());
		} else {
			// 创建一个心得节点
			LinkNode newNode = new LinkNode(obj);
			// 得到当前索引位置的节点
			LinkNode node = this.getLinkNode(index);
			if (index == 0) {
				front = newNode;
			} else {
				// 得到父节点
				LinkNode fNode = node.getParent();
				// 设置新的引用关系
				fNode.setChild(newNode);
				newNode.setParent(fNode);
			}
			// 设置心得引用关系
			newNode.setChild(node);
			node.setParent(newNode);

		}

	}

	/**
	 * 根据索引删除节点
	 * 
	 * @param index
	 *            ：索引
	 */
	public void deleteLinkNode(int index) {
		// 判断index是否有效
		if (this.getLength() < index || index < 0) {
			throw new java.lang.RuntimeException("下标越界" + index + ",size:"
					+ this.getLength());
		} else {
			// 得到当前索引位置的节点
			LinkNode node = this.getLinkNode(index);
			// 得到父节点
			LinkNode fNode = node.getParent();
			// 得到子节点
			LinkNode cNode = node.getChild();
			if (fNode == null) {
				front = cNode;
			} else if (cNode == null) {
				fNode.setChild(cNode);
			} else {
				fNode.setChild(cNode);
				cNode.setParent(fNode);
			}
		}
	}

	/**
	 * 根据索引取出节点
	 * 
	 * 
	 * @param index
	 *            ：第几个节点
	 * @return 根据节点返回的节点
	 */
	public LinkNode getLinkNode(int index) {
		if (this.getLength() < index || index < 0) {
			throw new java.lang.RuntimeException("下标越界" + index + ",size:"
					+ this.getLength());
		} else {

			int num = 1;
			LinkNode node = front;
			while (num != index) {
				node = node.getChild();
				num++;
			}

			return node;
		}
	}

	/**
	 * 得到链表长度
	 * 
	 * @return
	 */
	public int getLength() {
		int count = 0;
		if (front == null) {
			return count;
		}
		LinkNode node = front.getChild();
		while (null != node) {
			count++;
			node = node.getChild();
		}
		return count + 1;
	}

	/**
	 * 修改节点对象内容
	 * 
	 * @param index
	 *            -对象节点索引
	 * @param obj
	 *            修改对象内容
	 */
	public void UpdateLinkNode(int index, Object obj) {
		if (this.getLength() < index || index < 0) {
			throw new java.lang.RuntimeException("下标越界" + index + ",size:"
					+ this.getLength());
		} else {
			// 得到当前索引位置的节点
			LinkNode node = this.getLinkNode(index);
			node.setObj(obj);
		}
	}

	/**
	 * 遍历链表的方法
	 * 
	 * @param root
	 */
	public void printLinkList(LinkNode front) {
		int j = 0;
		if (null != front) {

			// 打印信息
			System.out.println(((Staff_Salary) front.getObj()).getName()
					+ " 工资:" + ((Staff_Salary) front.getObj()).getSalary());

			LinkNode temp = front.getChild();
			printLinkList(temp);
		}

	}

	/**
	 * 将对象加入数组
	 */
	public void setArrry(LinkNode front) {
		
		for (int i = 0; i < 20; i++) {
			array[i] = (Staff_Salary) getNextObj();
//			System.out.println(array);
		}
		Seqencing(array);

	}
	/**
	 * 得到链表的下一个节点
	 * @return
	 */
	public Object getNextObj() {

		Object data = front.getObj();
		front = front.getChild();
		return data;
	}
}