自己动手写数据结构之单向链表

【链表】
是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，
但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，
而顺序表相应的时间复杂度分别是O(㏒ n)和O(1)。 

【单向链表】 
 是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始
  一个节点包含两个域，一个信息域和一个指针域，指针域指向下一个节点，最后一个节点指向一个空值
 单向链表有一个头节点，可以不存储任何信息，包含一个指向第一个节点的指针
 特点:
 1.访问节点速度慢，需要从头节点一次遍历链表
 2.更新节点快，节点不需要移动，更改相应指针即可 

 

单向链表节点类定义如下：

 

public class Node<AnyType>{

	AnyType element;
	
	Node<AnyType> next;	

}

 

要实现单向列表的相关操作，可定义类SingleLinkedList如下：

public class SingleLinkedList<AnyType>{

	private static class Node<AnyType>{

		AnyType element;
		
		Node<AnyType> next;	
		
		public Node(AnyType element){
			this.element = element;
		}

	}
	
	private Node<AnyType> header = new Node<AnyType>(null);
	
	private int size = 0;
	
	public boolean isEmpty(){
		return size==0;
	}
	
	public void makeEmpty(){
		header = null;
	}
	
	public int size(){
		return size;
	} 
	
	/**
	 * Get element by index
	 * */
	public AnyType get(int index){		
		return getNode(index).element;
	}
	
	/**
	 * Add the element to the end of this list
	 * */
	public void add(AnyType element){
		add(new Node<AnyType>(element));
	}
	
	/**
	 * Inserts the specified element at the specified position in this list
	 * 插入逻辑：
	 * 1.创建一个新节点
	 * 2.将原index节点的前一个节点的指针指向新节点
	 * 3.将新节点的指针指向index节点
	 * 4.插入后，新节点的位置为index
	 * */
	public void add(int index,AnyType element){
		Node<AnyType> newNode = new Node<AnyType>(element);
		Node<AnyType> previous = getNode(index-1);
		//index节点
		Node<AnyType> node = previous.next;
		//将原index节点的前一个节点的指针指向newNode
		previous.next = newNode;
		//将newNode的指针指向index节点
		newNode.next = node;
		size++;
	}
	
	/**
	 * Inserts the specified element at the specified position in this list
	 * 删除逻辑：
	 * 1.获得index节点的前一个节点previousNode
	 * 2.获得index节点的后一个节点nextNode
	 * 3.将previousNode的指针指向nextNode
	 * */
	public void remove(int index){
		Node<AnyType> previous = getNode(index-1);
		Node<AnyType> next = previous.next.next;
		previous.next = next;
		size--;
	}

	
	/**
	 * 定义此方法是为了便于测试
	 * */
	public List<Integer> getElements(){
		if(isEmpty()){
			return null;
		}else{
			List<Integer> elements = new ArrayList<Integer>();
			Node<AnyType> node = (Node<AnyType>) header;
			while(node.next!=null){
				node = node.next;
				elements.add(((Element)node.element).getValue());
			}
			return elements;
		}
	}
	

	//private methods
	private Node<AnyType> getNode(int index){
		if(isEmpty()){
			throw new RuntimeException("List is empty");
		}
		int i = 0;
		Node<AnyType> node = header;
		while(i<=index){
			node = node.next;
			i++;
		}
		return node;
	}
	
	private void add(Node<AnyType> newNode){
		Node<AnyType> node = header;
		while(node.next!=null){
			node = node.next;
		}
		node.next = newNode;
		size++;
	}
		
}

 

如何实现链表反向：

/**
	 * 链表反向
	 * */
	public void reverse(){
		if(!isEmpty()){
			reverse(header.next,header.next.next);
		}		
	}

 

private void reverse(Node<AnyType> node,Node<AnyType> nextNode){
		if(nextNode.next!=null){
			reverse(nextNode,nextNode.next);			
		}else{
			//如果该节点是表尾，那么用头节点指向此节点
			header.next = nextNode;
		}	
		//该节点的指针指向前一个节点P，并将节点P的指针设置为空
		nextNode.next = node;
		node.next = null;
	}