- 浏览: 436240 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (158)
- J2SE (15)
- c/c++ (17)
- linux & ubuntu (20)
- js (18)
- algorithm (21)
- android (1)
- software (3)
- svn (1)
- db (6)
- other (19)
- css (5)
- go (1)
- html 5 (3)
- computer science (1)
- php (3)
- 创业 (8)
- EJB & jboss (1)
- TDD (1)
- jsp & servlet (2)
- http, tcp & ip (2)
- hibernate (1)
- json (1)
- 乐 (2)
- ps (2)
- netbeans (1)
- extjs (2)
- eclipse (4)
- 项目管理 (1)
- varnish (2)
- study abroad (1)
- python (1)
- erlang (1)
- math (1)
- shell (1)
- assembly (4)
- lucene (1)
- web (1)
- http (1)
- tcp & ip (1)
最新评论
-
yiguxianyun:
...
css li 不换行 -
stdayong:
...
netbeans 中使用 maven -
程序猿_星:
为啥会中文乱码啊
servlet 以 gzip 格式返回数据 -
huanhuan519:
感谢分享~
gdb 调试工具 -
heyl1234:
写过些js,对css还不熟。谢谢~
css li 不换行
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); } } } } }
------
发表评论
-
c - linkedlist
2012-05-10 14:52 1027c - linkedlist store ordere ... -
c - word counter (binary-tree)
2012-05-09 14:17 1670c - word counter (binary-tree) ... -
random select
2011-08-28 01:00 1172random select problem: ... -
sparse data structure - matrix
2011-08-18 20:03 1030sparse data structure sp ... -
max sub_sequence - c
2011-08-10 01:02 1038max sub_sequence - c /* ... -
binary search - c
2011-08-06 12:07 1043binary search - c (simple) ... -
bit_array - simple use
2011-05-28 23:47 970bit array,use less memory to de ... -
queue (用 java 简单实现)
2011-02-03 01:45 4007queue ------ 结构 线性存 ... -
Medians and Order Statistics (次序统计)
2011-01-03 14:36 2776Medians and Order Statistics - ... -
counting sort
2011-01-02 20:36 1525counting sort ------ counting ... -
quick sort
2011-01-01 20:26 1152quicksort ------ quicksort ove ... -
priority queue
2010-12-22 00:11 2223priority queue priority queue ... -
heap sort
2010-12-18 19:09 1169heapsort ------ heap 数据结构 hea ... -
merge sort
2010-12-01 23:37 1113merge sort 合并排序 ------ merge ... -
insertion sort
2010-10-28 00:21 1008insertion sort ------ insertio ... -
z 字型 读取 矩阵
2010-10-23 16:50 2141以 z 字型 读取 矩阵, ... -
排序算法:求 长度为 n的 数组中,最大的 m个数
2010-08-31 10:16 2585排序:数组 length=m,从其中中取出最大的 n 数字,n ... -
已排序数组 a,求其元素的绝对值 共有多少个不同的值
2010-08-29 20:41 1556已排序数组 a,求其元素的绝对值 共有多少个不同的值? ... -
binary search
2010-08-29 19:35 919binary search in sorted array: ... -
An Introduction to Algorithm 2nd 's contents
2010-08-11 23:02 1143算法导论(2nd) 结构 * <Introductio ...
相关推荐
循环的java源码压缩cs-实施-a-链表实验室 目标 用 Java 实现一个链表。 编写 ...这是一个简单节点的类定义: public class ListNode { public Object cargo; public ListNode next; public List
相信大家都明白 LinkedList 是基于双向链表而实现的,本篇文章主要讲解一下双向链表的实现,并且我们参考 LinkedList 自己实现一个单链表尝试一下。 什么是链表? 简单的来讲一下什么是链表:首先链表是一种线性的...
这是自己写的一个Java实现模拟数据结构中的LinkedList。实现其简单的添加节点功能
LinkedList与ArrayList都是List接口的具体实现类。下面将介绍如何实现一个简单的LinkedList,具有很好的参考价值,下面跟着小编一起来看下吧
java5 1.4.1 使用object表示泛型 1.4.2 基本类型的包装 1.4.3 使用接口类型表示泛型 1.4.4 数组类型的兼容性 1.5 利用java5泛性实现泛型特性成分 1.5.1 简单的泛型类和接口 1.5.2 自动装箱/拆箱....
java5 1.4.1 使用object表示泛型 1.4.2 基本类型的包装 1.4.3 使用接口类型表示泛型 1.4.4 数组类型的兼容性 1.5 利用java5泛性实现泛型特性成分 1.5.1 简单的泛型类和接口 1.5.2 自动装箱/拆箱....
linkedListjava单链表的实现和简单操作注意isCircle()这个函数是判断单链表是否成环的函数,由于是单链表所以头尾指针只有一个,所以出现环只能是大圈,最后一个和头结点成环,不可能出现中间“打结”的情况,我们...
用Java实现 的HotJava浏览器,显示了Java的魅力:跨平台、动感的Web、Internet计算。从此,Ja va被广泛接受并推动了Web的迅速发展,常用的浏览器现在均支持Java applet。另一方面,Java技术也不断更新。Java平台由...
简单实现ArrayList,实现动态数组 03-链表 抽象List设计思路 ArrayList2优化动态数组缩容 CircleLinkedList双向向链表 SingleCircleLinkedList单向链表 LinkedList双向链表实现解决约瑟夫环问题 04-栈 Stack利用java...
csci 211 作业 1 简单链接数据结构 截止日期:20131 年 10 月 14 日,星期一 该作业提供 Eclipse 调试器、JUnit 测试、测试驱动开发和实现链接数据结构的接触和经验。 概述 该作业要求您实现和测试堆栈、队列、双向...
与内部Java API实现相比,性能几乎没有差异。 接口包括: 堆 队列 排序队列 双端队列 放 地图 哈希表集 HashTableMap 执行基于数组,LinkedList和节点以及二进制搜索树 此外,这些数据类型还用于创建高效...
用一个队列来存放请求,所以只能按FIFO机制调度,你可以改用LinkedList,就可以简单实现一个优先级(优先级高的addFirst,低的addLast). 三.有能力将调用的边界从线程扩展到机器间(RMI) 四.分离过度耦合,如分离调用句柄...
│ Java面试题10.ArrayList LinkedList.mp4 │ Java面试题11.HashMap和HashTable的区别.mp4 │ Java面试题12.实现一个拷贝文件的类使用字节流还是字符串.mp4 │ Java面试题13.线程的实现方式 怎么启动线程怎么区分...
课时安排 总学时:52学时 授课:48学时 (含约20学时实验) 考试:4学时 预备知识 了解和使用操作系统,计算机的基本组成,简单的程序开发技术 参考教材 “Java ...
Java面试题10.ArrayList 和LinkedList的区别 Java面试题11.HashMap和HashTable的区别 Java面试题12.实现一个拷贝文件的工具类要使用字节流还是字符串 Java面试题13.线程的的实现方式?怎么启动线程?怎么区分线程? ...
set, list, queue这些接口间的区别,set不可重复, arraylist的实现和linkedlist的实现区别,HashMap, HashTable。涉及到各种效率问题等,里面最好阅读一下源码 集合的遍历方法和使用iterator来遍历的区别,集合...
示例:简易的客户端服务器通信 集合 集合框架总览 -、Iterator Iterable ListIterator 二、Map 和 Collection 接口Map 集合体系详解 HashMap LinkedHashMap TreeMap WeakHashMap Hashtable Collection 集合体系详解 ...
74、什么是java序列化,如何实现java序列化?或者请解释Serializable接口的作用。 51 75、描述一下JVM加载class文件的原理机制? 52 76、heap和stack有什么区别。 52 77、GC是什么? 为什么要有GC? 52 78、垃圾回收的...
java为数据结构中的列表定义了一个接口类java.util.list同时提供了3个实现类,分别是ArrayList、Vector、LinkedList使用; 生成不重复的随机数序列;列表、集合与数组的互相转换;java为数据结构中的映射定义一个接口...
31、java 中会存在内存泄漏吗,请简单描述。 11 32、abstract 的method 是否可同时是static,是否可同时是native,是否可同时是synchronized? 11 33、静态变量和实例变量的区别? 11 34、是否可以从一个static 方法...