`
tangyanbo
  • 浏览: 262531 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

单向链表

阅读更多

【链表】
是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(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;
	}

 

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics