Java数据结构与算法_链表

     数组作为数据存储结构有一定的缺陷，在无序的数组中，搜索是低效的；而在有序数组中，插入效率又很低；不管在哪一种数组中删除效率都很低。况且一个数组创建后，它的大小不能改变，链表就能够解决数组插入、删除效率低问题。

     链表在表头插入和删除速度很快。仅需要改变一两个引用值，所以花费O(1)的时间。平均起来，查找、删除和指定节点后面插入都需要搜索链表中一般链接点，需要O(N)次比较。在数组中执行这些操作也需要O(N)次比较，但是链表任然要快一些，因为要插入和删除链接点时，链表不需要移动任何东西。

      链表是继数组后第二中使用得最广泛的通用存储结构。

 

下面的使用Java代码实现双向链表：

 

1:链表Interface

 

public interface ListX<E> {

	public int size(); // 表数据总数

	public boolean isEmpty(); // 是否为空
	
	 /**
     * Appends the specified element to the end of this list
	  * @param e Element will be appends to the list
	  * @return
	  */
	 boolean add(E e);
	 
	 /**
	  * Insert the element at the specified position in the list with specified element 
	  * @param index
	  * @param element
	  */
	 void add(int index, E element);
	 
	 /**
	  * Remove the element at the specified position in this list
	  * @param index
	  * @return
	  */
	 E remove(int index);
	 
	 
	 /**
	  * Removes the first element from the list 
	  * @param o
	  * @return
	  */
	 boolean removeFirst();
	 
	 /**
	  * Return the element at the specified position of list
	  * @param index
	  * @return
	  */
	 E get(int index);
	 
	 /**
	  * Return the element at the first position of list
	  * @param index
	  * @return
	  */
	 E getFirst();
	 
	 /**
	  * Return the element at the last position of list
	  * @return
	  */
	 E getLast();
	 
	 boolean contains(E e);
}

 

 

2：结点类Entry

      Entry是放在LinkedListX中的内部静态类

 

	/**
	 * 节点类， 代表链表中的每一个节点。 
	 * @author xusy
	 *
	 * @param <E>
	 */
	private static class Entry<E> {
		E element;
		Entry next;
		Entry previous;

		public Entry(E e, Entry<E> previous, Entry<E> next) {
			this.element = e;
			this.next = next;
			this.previous = previous;
		}
	}

 

 

3：链表LinkedListX

import java.util.NoSuchElementException;

public class LinkedListX<E> implements ListX<E> {
	private int size;
	private Entry header = new Entry<E>(null, null, null);

	public LinkedListX() {
		header.next = header.previous = header;
	}
	
	
	/**
	 * 节点类， 代表链表中的每一个节点。 
	 * @author xusy
	 *
	 * @param <E>
	 */
	private static class Entry<E> {
		E element;
		Entry next;
		Entry previous;

		public Entry(E e, Entry<E> previous, Entry<E> next) {
			this.element = e;
			this.next = next;
			this.previous = previous;
		}
	}

	public E getFirst() {
		if (size == 0)
			throw new NoSuchElementException();
		return (E) header.next.element;
	}

	public E getLast() {
		if (size == 0)
			throw new NoSuchElementException();
		return (E) header.previous.element;
	}

	public void addFirst(E element) {
		addBefore(element, header.next);
	}

	public void addLast(E element) {
		addBefore(element, header);
	}

	public boolean contains(E e) {
		int index = indexOf(e);
		return index != -1;
	}

	public E remove(Entry e) {
		e.previous.next = e.next;
		e.next.previous = e.previous;

		E element = (E) e.element;
		e.next = null;
		e.previous = null;
		e.element = null;

		size--;
		return element;
	}

	private int indexOf(E o) {
		int index = 0;
		if (o == null) {
			for (Entry e = header.next; e != header; e = e.next) {
				if (e.element == null)
					return index;
				index++;
			}
		} else {
			for (Entry e = header.next; e != header; e = e.next) {
				if (o.equals(e.element))
					return index;
				index++;
			}
		}
		return -1;
	}

	private void addBefore(E element, Entry entry) {
		Entry newEntry = new Entry<E>(element, entry.previous, entry);
		newEntry.next.previous = newEntry;
		newEntry.previous.next = newEntry;

		size++;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public boolean add(E e) {
		addLast(e);
		return true;
	}

	@Override
	public void add(int index, E element) {
		Entry entry = index(index);
		addBefore(element, entry);
	}

	private Entry index(int index) {
		if (index < 0 || index > size)
			throw new IndexOutOfBoundsException();

		Entry entry = header.next;
		while (index > 0) {
			entry = entry.next;
		}

		return entry;
	}

	@Override
	public E remove(int index) {
		Entry entry = index(index);
		return remove(entry);
	}

	@Override
	public boolean removeFirst() {
		if (size == 0)
			throw new NoSuchElementException();

		remove(header.next);

		return true;
	}

	@Override
	public E get(int index) {
		return (E) index(index).element;
	}

	public void insertSort(int[] array){
		int in,out,temp;
		for(out=1;out<array.length;out++){
			temp = array[out];
			in=out;
			while(in>0&&array[in]>temp){
				array[in]=array[in-1];
				in--;
			}
		array[in]=temp;
		}
	}
}