`
Fox_ed
  • 浏览: 3497 次
  • 性别: Icon_minigender_1
  • 来自: 上海
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

单链表的简单实现

    博客分类:
  • java
阅读更多
1、单链表的存储结构
/**
 * 单链表
 * @author fox
 *
 */
public class Node {
	private Object nodeValue;
	private Node nextNode;
	
	public Node() {
		nodeValue = null;
		nextNode = null;
	}
	
	public Node(Object item) {
		nodeValue = item;
		nextNode = null;
	}
	
	public Node(Object item, Node next) {
		nodeValue = item;
		nextNode = next;
	}

	public Object getNodeValue() {
		return nodeValue;
	}

	public void setNodeValue(Object nodeValue) {
		this.nodeValue = nodeValue;
	}

	public Node getNextNode() {
		return nextNode;
	}

	public void setNextNode(Node nextNode) {
		this.nextNode = nextNode;
	}
		
}

2、由于单链表是一种线性结构,所以他实现了LinearList接口。
关于LinearList接口,详情请查看http://fox-ed.iteye.com/blog/1775542
详细实现方法如下:
/**
 * 单链表的实现
 * @author fox
 *
 */
public class SingleLinkList implements LinearList {

	private Node head;
	public SingleLinkList() {
		head = null;
	}
	
	public SingleLinkList(Node node) {
		this.head = node;
	}
	
	public boolean isEmpty() {
		if(head == null) {
			return true;
		} else {
			return false;
		}
	}

	public int size() {
		int size = 0;
		Node temp = this.head;
		while(temp != null) {
			size++;
			temp = temp.getNextNode();
		}
		return size;
	}

	public Object get(int index) {
		checkIndex(index);
		Node temp = this.head;
		for(int i = 0; i < index; i++) {
			temp = temp.getNextNode();
		}
		return (Object)temp.getNodeValue();
	}

	public void set(int index, Object o) {
		checkIndex(index);
		Node node = this.head;
		for(int i = 0; i < index; i++) {
			node = node.getNextNode();
		}
		node.setNodeValue(o);
	}

	public boolean add(int index, Object o) {
		if(index < 0) {
			throw new IndexOutOfBoundsException("下标错误:"+index);
		}
		
		if(head == null) {
			head = new Node(o);
		} else {
			Node temp = this.head;
			if(index == 0) {
				this.head = new Node(o,temp);
			} else {
				int i =0;
				while(temp.getNextNode() != null && i < index - 1) {
					i++;
					temp = temp.getNextNode();
				}
				temp.setNextNode(new Node(o,temp.getNextNode()));
			}
		}
		return true;
	}

	public boolean add(Object o) {
		return add(Integer.MAX_VALUE,o);
	}

	public Object remove(int index) {
		checkIndex(index);
		Object oldObj = null;
		Node temp = this.head;
		if(index == 0) {
			oldObj = (Object)head.getNodeValue();
			this.head = temp.getNextNode();
			temp = null;
		} else {
			int i = 0;
			while(temp.getNextNode() != null && i < index - 1) {
				i++;
				temp = temp.getNextNode();
			}
			Node node = temp.getNextNode();
			oldObj = (Object) node.getNodeValue();
			temp.setNextNode(node.getNextNode());
			node = null;
		}
		return oldObj;
	}

	public void clear() {
		int size = this.size();
		if(size != 0) {
			for(int i = size - 1;i >= 0; i--) {
				this.remove(i);
			}
		}
	}
	
	private void checkIndex(int index) {
		if(index < 0 || index > this.size() - 1) {
			throw new IndexOutOfBoundsException("下标错误:"+index);
		}
	}

}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics