linkedlist - java 简单实现

 

linked list

 

链表，

 

------

特点:

 

linkedlist 相对于基于数组的 list:

* 在中间 插入 & 删除 时,效率较高,只影响 前结点的next指针 和 后结点的pre指针,

* 根据 index get() 时 效率较低,需要一个个查找

* 

 

------

结构：

 

每个元素包含：

* value 值，

* pre 前一个元素，

* next 后1个元素，

 

------

操作：

 

* search

O(n)

* insert

O(1)

* delete

O(1)

* Sentinels

用 一个 特殊值 表示不存在的值，以方便各种操作对空元素的判断，

* 

------

例子 (java 实现):

 

* java 类

 

package eric.algrathem.struct.linkedlist;

import java.util.ArrayList;
import java.util.List;

/**
 * structure for linkedlist
 * 
 * @author eric
 * @date 2011-2-11 上午03:27:26
 */
public class LinkedListStruct<E> {
	/** the header entry */
	private Entry<E> header;
	/** total entry count */
	private int size;

	public LinkedListStruct() {
		this.header = new Entry<E>(null, null, null);
		this.size = 0;
	}

	/**
	 * add at end
	 * 
	 * @param ele
	 */
	public boolean add(E ele) {
		if (size == 0) {
			header.element = ele;
			size++;
		} else {
			addAtEnd(ele);
		}
		return true;
	}

	/**
	 * add at specify position
	 * 
	 * @param ele
	 * @param index target index,index <= current size
	 * @return
	 */
	public boolean add(E ele, int index) {
		if (index < 0 || index > size) { // index invalid
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
		} else if (index == size) { // append at end
			return add(ele);
		} else { // add at position of one current element
			addBefore(ele, getEntry(index));
		}
		return true;
	}

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

	public void remove(int index) {
		remove(getEntry(index));
	}

	/** return size */
	public int size() {
		return size;
	}

	/**
	 * search,return first match element's index,if not found return -1
	 * 
	 * @param ele
	 * @return
	 */
	public int search(E ele) {
		return search(ele, 0);
	}

	/**
	 * search,search from specified index,return first match element's index,if not found return -1
	 * 
	 * @param ele
	 * @param start
	 * @return
	 */
	public int search(E ele, int start) {
		Entry<E> entry = getEntry(start);
		int index = start;
		while (index < size) {
			if (entry.element != null && entry.element.equals(ele)) {
				return index;
			}
			entry = entry.next;
			index++;
		}
		return -1;
	}

	/**
	 * search all,return all match element's index in a list
	 * 
	 * @param ele
	 * @return
	 */
	public List<Integer> searchAll(E ele) {
		return searchAll(ele, 0);
	}

	/**
	 * search all,search from specified index,return all match element's index in a list
	 * 
	 * @param ele
	 * @param start
	 * @return
	 */
	public List<Integer> searchAll(E ele, int start) {
		List<Integer> result = new ArrayList<Integer>();
		Entry<E> entry = getEntry(start);
		int index = start;
		while (index < size) {
			if (entry.element != null && entry.element.equals(ele)) {
				result.add(index);
			}
			entry = entry.next;
			index++;
		}
		return result;
	}

	/** single data entity,including data & two reference(previous,next) */
	private static class Entry<E> {
		E element;
		Entry<E> next;
		Entry<E> previous;

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

	/**
	 * insert before
	 * 
	 * @param ele
	 * @param entry
	 * @return
	 */
	private synchronized Entry<E> addBefore(E ele, Entry<E> entry) {
		Entry<E> newEntry = new Entry<E>(ele, entry, entry.previous);
		if (entry.previous != null) {
			entry.previous.next = newEntry;
		}
		entry.previous = newEntry;
		if (newEntry.previous == null) { // reset header
			header = newEntry;
		}
		size++;
		return newEntry;
	}

	/**
	 * add at end
	 * 
	 * @param ele
	 * @return
	 */
	private synchronized Entry<E> addAtEnd(E ele) {
		Entry<E> end = getEntry(size - 1);
		Entry<E> newEntry = new Entry<E>(ele, null, end);
		end.next = newEntry;
		size++;
		return newEntry;
	}

	/**
	 * get by index,index is the order of entry (start by 0)
	 * 
	 * @param index
	 * @return
	 */
	private synchronized Entry<E> getEntry(int index) {
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
		}
		Entry<E> entry = header;
		while (index-- > 0) {
			entry = entry.next;
		}
		return entry;
	}

	/**
	 * insert before
	 * 
	 * @param ele
	 * @param entry
	 * @return
	 */
	private synchronized void remove(Entry<E> entry) {
		if (entry.previous != null) {
			entry.previous.next = entry.next;
		} else { // header is the target to remove,reset header
			header = (entry.next == null ? new Entry<E>(null, null, null) : entry.next);
		}
		if (entry.next != null) {
			entry.next.previous = entry.previous;
		}
		entry.previous = entry.next = null;
		entry = null;
		size--;
	}
}

 

 

* junit 测试类

 

package eric.algrathem.struct.linkedlist;

import java.util.List;

import junit.framework.Assert;
import junit.framework.TestCase;

import org.junit.Test;

/**
 * test case for LinkedListStruct
 * 
 * @author eric
 * @date 2011-2-11 下午08:50:35
 */
public class LinkedListStructTest extends TestCase {
	@Test
	public void testAdd() {
		LinkedListStruct<Integer> list = new LinkedListStruct<Integer>();
		int size = 10;
		for (int i = 0; i < size; i++) {
			list.add(i);
		}

		for (int i = 0; i < size; i++) {
			Assert.assertTrue(i == list.get(i));
		}

		list.add(100, 5);
		Assert.assertTrue(100 == list.get(5));
		Assert.assertTrue(4 == list.get(4));
		Assert.assertTrue(5 == list.get(6));
		Assert.assertTrue(6 == list.get(7));
	}

	@Test
	public void testRemove() {
		LinkedListStruct<Integer> list = new LinkedListStruct<Integer>();
		int size = 20;
		int[] removeIndexArr = { 3, 8, 15 };
		for (int i = 0; i < size; i++) {
			list.add(i);
		}
		for (int i = 0; i < removeIndexArr.length; i++) {
			list.remove(removeIndexArr[i] - i);
		}

		Assert.assertTrue(list.size() == size - removeIndexArr.length);
		int curRemove = 0;
		int fix = 0;
		for (int i = 0; i < list.size(); i++) {
			if (curRemove < removeIndexArr.length && i == (removeIndexArr[curRemove] - curRemove)) {
				fix++;
				curRemove++;
			}
			Assert.assertTrue(list.get(i) == i + fix);
		}
	}

	@Test
	public void testSearch() {
		LinkedListStruct<Integer> list = new LinkedListStruct<Integer>();
		int size = 10;
		int repeat = 3;
		for (int i = 0; i < repeat; i++) {
			for (int j = 0; j < size; j++) {
				list.add(j);
			}
		}
		for (int x = 0; x < size; x++) {
			Assert.assertEquals(x, list.search(x));
			for (int y = 0; y < repeat; y++) {
				Assert.assertEquals(x + size * y, list.search(x, size * y));
			}
		}
	}

	@Test
	public void testSearchAll() {
		LinkedListStruct<Integer> list = new LinkedListStruct<Integer>();
		int size = 10;
		int repeat = 3;
		for (int i = 0; i < repeat; i++) {
			for (int j = 0; j < size; j++) {
				list.add(j);
			}
		}
		for (int x = 0; x < size; x++) {
			// searchAll(ele)
			List<Integer> result = list.searchAll(x);
			Assert.assertEquals(result.size(), repeat);
			for (int y = 0; y < repeat; y++) {
				Assert.assertTrue(result.get(y) == x + y * size);
			}

			// searchAll(ele,start)
			for (int z = 0; z < repeat; z++) {
				List<Integer> resultPart = list.searchAll(x, z * size);
				Assert.assertEquals(resultPart.size(), repeat - z);
				for (int z1 = 0; z1 < resultPart.size(); z1++) {
					Assert.assertTrue(resultPart.get(z1) == ((z + z1) * size) + x);
				}
			}
		}
	}
}

 
------