手动实现单链表和循环链表

1.单链表的实现：

package com.sun;public class DanLink {	public static void main(String[] args) {		DanLink link = new DanLink();		link.addFirstNode("sunchaung");		link.add(1, "张乐");		link.addTailNode("习大大");		link.addFirstNode("maozed");		// link.deleteByData("习大大");		// link.deleteByPos(2);		Node findByData = link.findByData("习大大");		findByData.display();		Node findByPos = link.findByPos(3);		findByPos.display();		link.displayAllNodes();	}	PRivate Node first; // 定义一个头结点	private int pos = 0;// 节点的位置	private int size;	public DanLink() {		this.first = null;		this.size = 0;	}	// 插入一个头节点	public void addFirstNode(Object data) {		Node node = new Node(data);		node.next = first;		first = node;		size++;	}	// 插入一个尾节点	public void addTailNode(Object data) {		if (size == 0 || first == null) {			return;		}		Node node = first;		while (node.next != null) {			node = node.next;			if (node.next == null) {				break;			}		}		// 找到了最后一个节点		Node node2 = new Node(data);		node.next = node2;		node2.next = null;		size++;	}	// 删除一个头结点,并返回头结点	public Node deleteFirstNode() {		if (null == first || size == 0) {			return null;		}		if (size == 1) {			Node node = first;			first.data = null;			first.next = null;			size--;			return node;		}		Node tempNode = first;		first.data = null;		first.next = null;		first = tempNode.next;		return tempNode;	}	// 在任意位置插入节点 在index的后面插入	public void add(int index, Object data) {		if (!(index <= size)) {			return;		}		if (index == 0) {			addFirstNode(data);			return;		}		if (index == size) {			addTailNode(data);			return;		}		Node node = new Node(data);		Node current = first;// 前一个		Node previous = first;// 后一个		while (pos != index) {			if (current.next == null) {				return;			}			previous = current;			current = current.next;			pos++;		}		previous.next = node;		node.next = current;		size++;		pos = 0;	}	// 删除任意位置的节点	public Node deleteByPos(int index) {		if (index < 0 || index >= size) {			return null;		}		if (size == 0 || first == null) {			return null;		}		if (index == 0 && size == 1) {			Node node = first;			first.next = null;			first.data = null;			first = null;			return node;		}		Node current = first;		Node previous = first;		while (pos != index) {			if (current.next == null) {				return null;			}			previous = current;			current = current.next;			pos++;		}		if (current == first) {			first = first.next;			pos = 0;			size--;		} else if (index == (size - 1)) {			current.data = null;			current.next = null;			previous.next = null;			pos = 0;			size--;		} else {			previous.next = current.next;			pos = 0;			size--;		}		return current;	}	// 根据节点的data删除节点(仅仅删除第一个)	public Node deleteByData(Object data) {		Node current = first;		Node previous = first; // 记住上一个节点		while (current.data != data) {			if (current.next == null) {				return null;			}			previous = current;			current = current.next;		}		if (current == first) {			deleteFirstNode();		} else if (current.next == null) {			current.data = null;			current.next = null;			previous.next = null;			size--;		} else {			previous.next = current.next;			size--;		}		return current;	}	// 显示出所有的节点信息	public void displayAllNodes() {		Node current = first;		while (current != null) {			current.display();			current = current.next;		}		System.out.println();	}	// 根据位置查找节点信息	public Node findByPos(int index) {		if (index < 0 || index >= size) {			return null;		}		Node current = first;		if (pos != index) {			current = current.next;			pos++;		}		return current;	}	// 根据数据查找节点信息	public Node findByData(Object data) {		Node current = first;		while (current.data != data) {			if (current.next == null)				return null;			current = current.next;		}		return current;	}}class Node {	protected Node next; // 指针域	public Object data;// 数据域	public Node(Object data) {		this.data = data;	}	// 显示此节点	public void display() {		System.out.print(data + " ");	}}2.循环链表的实现
package com.sun;public class DcycleLink {public static void main(String[] args) {DcycleLink link = new DcycleLink();link.addTail("张乐");link.addHead("sunchaung");link.addHead("哈哈");link.print();}private Node head;private Node tail;private int count;public DcycleLink() {}public void print() {Node node = head;for (int i = 0; i < count; i++) {System.out.print("  "+node.element);node = node.next;}}// 循环链表的末尾增加节点public Object addTail(String element) {if (null == head) {Node node = new Node(element, null, null);head = node;tail = node;head.next = tail;head.prev = tail;tail.next = head;tail.prev = head;count += 1;} else {Node tmp = new Node(element, null, null);tail.next = tmp;tmp.prev = tail;tail = tmp;tail.next = head;head.prev = tail;count += 1;}return element;}// 循环链表的头节点增加节点public Object addHead(String element) {if (null == head) {Node node = new Node(element, null, null);head = node;tail = node;head.next = tail;head.prev = tail;tail.next = head;tail.prev = head;count += 1;} else {Node tmp = new Node(element, null, null);tmp.next = head;head.prev = tmp;head = tmp;head.prev = tail;tail.next = head;count += 1;}return element;}// 向已知位置添加节点public Object addNext(String element, int index) {if (index < 0) {throw new IllegalArgumentException("index can't smaller than 0.");}if (null == head && index > 0) {throw new RuntimeException("link is empty add nothing.");}if (null == head && 0 == index) {return addTail(element);}if (null != head && index > 0) {if (index == count) {Node tmpNode = searchNext(index);Node tmpNextNode = tmpNode.next;Node newNode = new Node(element, null, null);tmpNode.next = newNode;newNode.prev = tmpNode;newNode.next = tmpNextNode;tmpNextNode.prev = newNode;tail = newNode;} else {Node tmpNode = searchNext(index);Node tmpNextNode = tmpNode.next;Node newNode = new Node(element, null, null);tmpNode.next = newNode;newNode.prev = tmpNode;newNode.next = tmpNextNode;tmpNextNode.prev = newNode;}}return element;}// 删除指定节点public Object delete(final int index) {if (index < 0) {throw new IllegalArgumentException("index can't smaller than 0.");} else { // >=0if (0 == index) {return deleteHead();} else { // index>0if (index >= count) {int tmpIndex = index % count;if (tmpIndex == count - 1) {Node tmpNode = searchNext(tmpIndex);tmpNode.prev.next = tmpNode.next;tmpNode.next.prev = tmpNode.prev;tmpNode.prev = null;tmpNode.next = null;return tmpNode.element;} else {Node tmpNode = searchNext(tmpIndex);Node tmpPreNode = tmpNode.prev;tmpNode.prev.next = tmpNode.next;tmpNode.next.prev = tmpNode.prev;tmpNode.prev = null;tmpNode.next = null;tail = tmpPreNode;return tmpNode.element;}} else { // 0<index<countif (index == count - 1) {Node tmpNode = searchNext(index);tmpNode.prev.next = tmpNode.next;tmpNode.next.prev = tmpNode.prev;tmpNode.prev = null;tmpNode.next = null;return tmpNode.element;} else {Node tmpNode = searchNext(index);Node tmpPreNode = tmpNode.prev;tmpNode.prev.next = tmpNode.next;tmpNode.next.prev = tmpNode.prev;tmpNode.prev = null;tmpNode.next = null;tail = tmpPreNode;return tmpNode.element;}}}}}// 删除头节点public Object deleteHead() {if (null == head) {throw new RuntimeException("link is empty, delete nothing.");} else {Object del = head.element;Node tmp = head.next;head.next = null;head.prev = null;tmp.prev = null;head = tmp;head.prev = tail;tail.next = head;count -= 1;return del;}}// 删除尾节点public Object deleteTail() {if (null == head) {throw new RuntimeException("link is empty, delete nothing.");} else {Object del = tail.element;// 临时节点是为节点的前一个节点Node tmp = tail.prev;// 尾节点的前一个节点要断开tail.prev = null;// 尾节点的下一个解释要断开tail.next = null;head.prev = null;// 临时节点的下一个节点要断开tmp.next = null;// 尾节点是临时节点tail = tmp;head.prev = tail;tail.next = head;count -= 1;return del;}}// 查询节点的值private Node searchNext(int index) {if (null == head) {throw new RuntimeException("link is empty, find nothing.");} else {Node tmphead = head;for (int i = 0; i < index; i++) {tmphead = tmphead.next;}return tmphead;}}// 查询节点的位置public int search(String element) {if (null == head) {throw new RuntimeException("link is empty, delete nothing.");} else {Node tmphead = head;Node tmptail = tail;for (int i = 0; i <= count / 2; i++) {if (element.equals(tmphead.element)) {return i;}if (element.equals(tmptail.element)) {return count - 1 - i;}tmphead = tmphead.next;tmptail = tmptail.prev;}return -1;}}// 节点的长度public int size() {return count;}private class Node {private Object element;private Node next;private Node prev;public Node(String pelement, Node pnext, Node pprev) {this.element = pelement;this.next = pnext;this.prev = pprev;}}}