每篇笔记都会附上随书的Applet演示程序，有算法看不明白的，可以下载Applet运行起来（直接打开html文件即可），可以很容易地看清楚算法的每一步。
链表
链表简单的说就是个对象链，一个对象里包含另一个对象的引用。链表类的成员只有一个：这个链表的第一个链接点。只要通过第一个链接点，就能得到链表里所有的其它链接点。下面是一个链表的实现：
package dsaa.array;
/**
* @(#)LinkList.java 2008-12-27 下午07:02:17
*
* @author Qiu Maoyuan
* Link List
*/
public class LinkList<E> {
private Link first;
public void addFirst(E value){
Link newElement = new Link(value);
newElement.next = first;
first = newElement;
}
public E getFirst(){
if(isEmpty())
throw new IllegalStateException("Linklist is empty");
return first.element;
}
public boolean isEmpty(){
return first == null;
}
public E removeFirst(){
if(isEmpty())
throw new IllegalStateException("Linklist is empty");
E value = first.element;
first = first.next;
return value;
}
public boolean delete(E element){
if(isEmpty())
return false;
Link current = first;
Link previous = first;
while(!element.equals(current.element)){
if(current.next == null){
return false;
} else {
previous = current;
current = current.next;
}
}
if(current == first)
first = first.next;
else
previous.next = current.next;
return true;
}
@Override
public String toString(){
StringBuilder buffer = new StringBuilder();
Link current = first;
while(current != null){
buffer.append(current.toString());
current = current.next;
}
return buffer.toString();
}
private class Link{
private E element;
private Link next;
public Link(E element){
this.element = element;
}
@Override
public String toString(){
return "[" + element.toString() + "]";
}
}
}
双端链表与普通链表的区别就是：双端链表多了一个对链表尾部元素的引用以及一个用于在尾部增加链拉点的addLast()方法。
package dsaa.array;
/**
* @(#)LinkList.java 2008-12-27 下午07:02:17
*
* @author Qiu Maoyuan
* Link List
*/
public class LinkList<E> {
private Link first;
private Link last;
public void addFirst(E value){
Link newElement = new Link(value);
if(isEmpty()){
last = newElement;
}
newElement.next = first;
first = newElement;
}
public E getFirst(){
if(isEmpty())
throw new IllegalStateException("Linklist is empty");
return first.element;
}
public boolean isEmpty(){
return first == null;
}
public E removeFirst(){
E value = getFirst();
first = first.next;
return value;
}
public boolean delete(E element){
if(isEmpty())
return false;
Link current = first;
Link previous = first;
while(!element.equals(current.element)){
if(current.next == null){
return false;
} else {
previous = current;
current = current.next;
}
}
if(current == first)
first = first.next;
else
previous.next = current.next;
if(current == last)
last = previous;
return true;
}
public void addLast(E value){
Link newElement = new Link(value);
if(isEmpty()){
first = newElement;
}else{
last.next = newElement;
}
last = newElement;
}
@Override
public String toString(){
StringBuilder buffer = new StringBuilder();
Link current = first;
while(current != null){
buffer.append(current.toString());
current = current.next;
}
return buffer.toString();
}
private class Link{
private E element;
private Link next;
public Link(E element){
this.element = element;
}
@Override
public String toString(){
return "[" + element.toString() + "]";
}
}
}
链表的效率
链表在表头的插入和删除操作都很快，只需要O(1)级别的时间。删除指定链接点的操作和数组一样，需要O(N)级别的时间。但是链表仍然比数组快得多，因为不需要像数组那样删除元素后还要移动元素。
链表比数组优越的另一个地方是：链表需要多少长度就可以分配多少长度，而数组的长度在创建时就是固定了的。尽管有Vector或者ArrayList这样可扩展长度的数组，但是它们只允许以固定的增量扩展，在内存的使用效率上还是比链表低。
下面是一个用
链表实现的栈：
package dsaa.array;
import java.util.EmptyStackException;
/**
* @(#)LinkStack.java 2008-12-28 上午04:21:08
*
* @author Qiu Maoyuan
* Stack
*/
public class LinkStack<E> {
private LinkList<E> stackLinkList;
public LinkStack(){
stackLinkList = new LinkList<E>();
}
public void push(E value){
stackLinkList.addFirst(value);
}
public E peek(){
E element = null;
try{
element = stackLinkList.getFirst();
}catch(IllegalStateException ex){
throw new EmptyStackException();
}
return element;
}
public E pop(){
E element = null;
try{
element = stackLinkList.removeFirst();
}catch(IllegalStateException ex){
throw new EmptyStackException();
}
return element;
}
public boolean isEmpty(){
return stackLinkList.isEmpty();
}
}
链表实现的队列：
package dsaa.array;
/**
* @(#)LinkQueue.java 2008-12-28 上午04:27:07
*
* @author Qiu Maoyuan
* Link Queue
*/
public class LinkQueue<E> {
private LinkList<E> queueLinkList;
public LinkQueue(int size){
queueLinkList = new LinkList<E>();
}
public E peek(){
return queueLinkList.getFirst();
}
public void insert(E value){
queueLinkList.addLast(value);
}
public E remove(){
return queueLinkList.removeFirst();
}
public boolean isEmpty(){
return queueLinkList.isEmpty();
}
}
一写完代码发现链表是个好东西，Stack和Queue的实现变得很容易
在写这些笔记的代码时，我都采用TDD的方式，上一章写Stack和Queue的测试代码完全可以直接用在LinkStack和LinkQueue上。。。针对接口测试……嗯，也许一开始就应该对接口进行测试。
有序链表，就不多说了，看名字就知道意思了
插入元素的实现就是先遍历找准位置，然后把新增链接点的next指向previous的next（也就是current），再把previous的next指向新增的这个链接点。然后注意处理一下特殊情况（比如正好插入位置是在链表头）。有序链表的效率还是比数组高：插入时和数组一样只需要O(N)级别的查找时间，但插入之前不需要像数组那样移动元素。
下面是一个有序链表的实现：
package dsaa.array;
/**
* @(#)SortedLinkList.java 2008-12-28 下午02:16:35
*
* @author Qiu Maoyuan
* Sorted LinkList
*/
public class SortedLinkList<E extends Comparable<E>> {
private Link first;
public void add(E value){
Link newElement = new Link(value);
if(isEmpty()){
first = newElement;
}else{
Link current = first;
Link previous = null;
while(!endOfLink(current) && current.element.compareTo(value)>=0){
previous = current;
current = current.next;
}
if(!endOfLink(current)){
newElement.next = current;
}
if(current == first)
first = newElement;
else
previous.next = newElement;
}
}
public E getFirst(){
if(isEmpty())
throw new IllegalStateException("Linklist is empty");
return first.element;
}
public boolean isEmpty(){
return first == null;
}
public E remove(){
E value = getFirst();
first = first.next;
return value;
}
public boolean delete(E element){
if(isEmpty())
return false;
Link current = first;
Link previous = first;
while(!element.equals(current.element)){
if(endOfLink(current.next)){
return false;
} else {
previous = current;
current = current.next;
}
}
if(current == first)
first = first.next;
else
previous.next = current.next;
return true;
}
private boolean endOfLink(Link link) {
return link == null;
}
@Override
public String toString(){
StringBuilder buffer = new StringBuilder();
Link current = first;
while(current != null){
buffer.append(current.toString());
current = current.next;
}
return buffer.toString();
}
private class Link{
private E element;
private Link next;
public Link(E element){
this.element = element;
}
@Override
public String toString(){
return "[" + element.toString() + "]";
}
}
}
给有序列表添加一个简单的带数组参数的构造方法，就可以用这个链表给一个数组进行排序，这种排序方法叫
表插入排序法。表插入排序法的效率比数组插入排序法（第2章的插入排序法）还高些：构造有序链表时平均需要N^2/2次比较，时间复杂度为O(N^2)，跟数组插入排序法花在“比较”上的时间级别一样，但数组插入排序法花在复制上的时间级别为O(N)，而表插入排序法花在复制上的时间级别为O(N)。
package dsaa.array;
/**
* @(#)SortedLinkList.java 2008-12-28 下午02:16:35
*
* @author Qiu Maoyuan
* Sorted LinkList
*/
public class SortedLinkList<E extends Comparable<E>> {
private Link first;
public SortedLinkList(){}
public SortedLinkList(E[] array){
for(E element : array){
add(element);
}
}
public void add(E value){
Link newElement = new Link(value);
if(isEmpty()){
first = newElement;
}else{
Link current = first;
Link previous = null;
while(!endOfLink(current) && current.element.compareTo(value)>=0){
previous = current;
current = current.next;
}
if(!endOfLink(current)){
newElement.next = current;
}
if(current == first)
first = newElement;
else
previous.next = newElement;
}
}
public E getFirst(){
if(isEmpty())
throw new IllegalStateException("Linklist is empty");
return first.element;
}
public boolean isEmpty(){
return first == null;
}
public E remove(){
E value = getFirst();
first = first.next;
return value;
}
public boolean delete(E element){
if(isEmpty())
return false;
Link current = first;
Link previous = first;
while(!element.equals(current.element)){
if(endOfLink(current.next)){
return false;
} else {
previous = current;
current = current.next;
}
}
if(current == first)
first = first.next;
else
previous.next = current.next;
return true;
}
private boolean endOfLink(Link link) {
return link == null;
}
@Override
public String toString(){
StringBuilder buffer = new StringBuilder();
Link current = first;
while(current != null){
buffer.append(current.toString());
current = current.next;
}
return buffer.toString();
}
private class Link{
private E element;
private Link next;
public Link(E element){
this.element = element;
}
@Override
public String toString(){
return "[" + element.toString() + "]";
}
}
}
可以这样使用这个有序链表：
/**
* 表插入排序法
* @param <T>
* @param array
*/
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void listInsertionSort(T[] array){
SortedLinkList linkList = new SortedLinkList(array);
T[] newArray = (T[])new Comparable[array.length];
for(int i=0; i<newArray.length; i++){
newArray[i] = (T)linkList.remove();
}
array = newArray;
}
[Java的泛型真恶心......
]
还有一种链表叫
双向链表，就是既可以向前遍历，又可以向后遍历的链表。这种链表的链接点内部有两个成员：previous和next。插入和删除的时候需要多操作一个引用。
分享到：
相关推荐
本文将基于《Java数据结构和算法》学习笔记中的“栈和队列”部分进行深入探讨。 栈（Stack）是一种线性数据结构，遵循后进先出（LIFO, Last In First Out）的原则。在栈中，元素的添加（压栈）和移除（弹栈）都是在...
### Java数据结构与算法——学习笔记 #### 一、引言 在计算机科学领域，**数据结构**与**算法**是两个极其重要的概念。数据结构指的是数据的组织方式，而算法则是解决特定问题的一系列步骤。这两者是编程的基础，...
本资料集是基于Java语言的实现，由著名计算机科学家Mark Allen Weiss所著的《数据结构与问题求解——java语言描述》（第三版）的源码。该书通过丰富的实例和深入的理论讲解，帮助读者理解和掌握各种经典的数据结构...
在哈工大的《数据结构与算法》以及...而其中的C/C++/JAVA/Python的学习笔记和资料则为深入理解和应用这些语言提供了丰富的素材。无论你是准备考试、做项目，还是进行个人学习，这个资源包都是一个不可多得的宝藏。
标题和描述中提到的是一份源自字节跳动内部的数据结构刷题学习笔记，这份笔记在GitHub上引起广泛关注，被认为是一份有助于提升编程能力，尤其是对于准备字节跳动面试的程序员极具价值的资源。主要关注点在于各种排序...
通过《数据结构——C++实现》（第二版）的学习，读者不仅能掌握各种数据结构的原理，还能熟悉C++编程，为后续的软件开发和算法设计打下坚实基础。同时，书中提供的源代码是宝贵的实践资源，可以帮助读者在实践中学习...
数据结构是计算机科学中至关重要的基础概念，它们用于有效地组织和管理数据，以便进行高效的存储、检索和操作。本文将深入探讨单链表这一常见数据结构，并与其他数据结构如数组进行对比。 单链表是一种线性数据结构...
2. **数据结构详解**：数据结构是算法的基础，课件可能涉及数组、链表、栈、队列、树（二叉树、平衡树如AVL和红黑树）、图、哈希表等。理解它们的性质和操作，对于优化算法至关重要。 3. **算法实例与应用**：通过...
在学习数据结构时，我们通常会关注数据的存储方式和相关的算法设计。郝斌老师的自学数据结构大纲笔记1为我们提供了一个基础的学习路径。 首先，数据结构的定义包括两个主要方面：个体数据的存储和个体间关系的存储...
本文通过对《Java基础复习笔记05数据结构-栈》的解析，详细介绍了栈的基本概念、操作方法以及应用场景，并提供了栈的两种实现方式——顺序实现与链表实现的详细说明。理解这些知识点对于深入学习数据结构与算法至关...
5. **数据结构与算法**：游戏中的物体位置、碰撞检测等都需要高效的数据结构（如数组、链表、队列、栈等）和算法（如搜索、排序、图遍历等）来处理。 6. **游戏逻辑**：实现游戏规则，如角色移动、碰撞检测、得分...
在描述中提到的“大学生 C/C++/JAVA/Python数据结构学习笔记和资料大全”，这是针对编程初学者的资源集合，涵盖了计算机科学中非常基础且重要的概念——数据结构。数据结构是计算机存储、组织数据的方式，包括数组、...
【描述】提到的"大学生 C/C++/JAVA/Python数据结构学习笔记和资料大全"则涵盖了计算机科学基础课程中的核心主题——数据结构。数据结构是计算机存储、组织数据的方式，它是算法分析的基础，直接影响程序的效率。C、...
- 该书籍专注于使用Java实现常见的数据结构（如链表、树、图等）和算法（排序、查找等），对于提高编程能力非常有帮助。 - 对于希望在Java中实现高效数据处理的学习者来说，这本书是不可或缺的。 ### 高级主题 1...
下午的软件设计部分则更加注重设计实践能力，包括数据流图的绘制与修正、数据库设计、UML建模、常用数据结构的程序实现（如链表、栈、二叉树、图）以及一些经典算法（如动态规划法、分治法、回溯法）。编程语言方面...
这本书系统地介绍了软件工程师面试中常遇到的算法和数据结构问题，涵盖了数组、链表、栈、队列、树等基础数据结构以及排序、查找、递归等基本算法。书中每个问题都配有详细的解题思路和代码实现，对于理解和应用这些...
3. **数据结构**：数组、链表、栈、队列、树、图等基本数据结构及其操作，以及排序和查找算法。 4. **算法**：贪心、动态规划、分治、回溯等算法思想，以及常用算法的分析与实现。 5. **操作系统**：进程管理、内存...
计算机基础知识包括数据结构（如数组、链表、树和图）、算法（排序、搜索、递归等）、操作系统原理（进程与线程、内存管理、I/O操作）、网络基础（TCP/IP协议、HTTP协议、客户端-服务器模型）以及数据库理论（关系型...
例如，`java.util`包中的`ArrayList`和`LinkedList`可以用来实现动态数组和链表，`PriorityQueue`可用于优先队列的构建，这些数据结构在许多算法中都是基础。同时，Java的异常处理机制和泛型特性使得代码更加健壮且...