linklist.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 89 行

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//16 Mar 2008
package cn.edu.whu.iss.algorithm.unit10;

import static cn.edu.whu.iss.algorithm.basictools.BasicSortTool.*;
import cn.edu.whu.iss.algorithm.unit10.datastruct.LinkNode;

public class LinkList<T>{
	private LinkNode<T> head,tail;

	private LinkNode<T> sentinel = new LinkNode(null);
	
	public LinkList() {
		super();
		head = sentinel;
		tail = sentinel;
		sentinel.setNext(sentinel);
		sentinel.setHead(sentinel);
	}
	
	public void addHead(T e){
		LinkNode<T> node = new LinkNode<T>(e);
		addHead(node);
	}
	
	private void addHead(LinkNode<T> node){
		head.setHead(node);
		node.setNext(head);
		head = node;
	}
	
	public void addTail(T e){
		LinkNode<T> node = new LinkNode<T>(e);
		addTail(node);
	}
	
	private void addTail(LinkNode<T> node){
		node.setHead(tail);
		tail.setNext(node);
		tail = node;
	}
	
	public T removeHead(){
		return remove(head);
	}
	
	private T remove(LinkNode<T> node){
		node.getHead().setNext(node.getNext());
		node.getNext().setHead(node.getHead());
		if(node==head){
			head=node.getNext();
		}else if(node==tail){
			tail=node.getHead();
		}
		return node.getObject();
	}
	
	public T remove(T e){
		LinkNode<T> node = head;
		while(compare(e, node.getObject())!=0){
			node = node.getNext();
		}
		remove(node);
		return e;
	}
	
	private void addAfterNode(LinkNode<T> head,LinkNode<T> node){
		LinkNode<T> tmp = head;
		if(head==sentinel){
			node.setNext(head);
			head.getNext().setHead(node);
			head=node;
		}
	}
	
	public T removeTail(){
		return remove(tail);
	}

}