数据结构中的单向链表
PASCAL语言之父、图灵奖得主尼古拉斯·沃斯(Niklaus Wirth)曾有一句在计算机领域几乎人尽皆知的名言：“算法+数据结构=程序”（Algorithm+Data Structures=Programs）。
数据结构指的是是计算机存储、组织数据的方式。其中数据的逻辑结构分为线性结构和非线性结构。
线性结构是一个有序数据元素的集合，其数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
最基础的两种表示元素集合的方式就是数组和链表。
数组指的是有序的元素序列。其中一维数组是线性的数据结构。数组的优点是通过索引可以访问任意元素，查找快。数组的缺点是在初始化数组的时候，就要知道数组的元素数量，而且插入和删除元素非常复杂。
链表就很好地解决了数组的缺点，其使用的空间大小和元素数量成正比，即不需要提供初始化的大小，而且插入和删除元素比较简单，不会“牵一发而动全身”。链表的缺点是需要通过引用访问任意元素，查找很复杂。
链表是一种递归的数据结构。一般链表分为单向链表和双向链表两种实现。
单向链表（单链表、线性链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过从头部开始，依序往下读取。而双向链表（双链表）的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
下面通过Java语言实现单向链表，来展示链表的相关操作。
Java实现单向链表
单向链表的每个节点只需要定义两个属性：当前节点的元素，下一个节点。
class Node{
Item item;
Node node;
}
使用链表实现栈
栈是一种先进后出(FILO)的数据结构，如果通过数组实现栈，则要考虑数组扩容的问题，可以通过链表来解决这个问题。
下面通过链表实现栈，并借此演示了在链表的头部增加节点以及除链表头部节点。
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack;
public interface Stack<Item> {
/**
* add an item
*
* @param item
*/
void push(Item item);
/**
* remove the most recently added item
*
* @return
*/
Item pop();
/**
* is the stack empty?
*
* @return
*/
boolean isEmpty();
/**
* number of items in the stac
*/
int size();
}
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.impl;
import net.ijiangtao.tech.algorithms.algorithmall.datastructure.stack.Stack;
import java.util.Iterator;
/**
* 链表实现可迭代的栈
* @param <Item>
* @author ijiangtao.net
*/
public class IterableLinkedListStack<Item> implements Stack<Item>,Iterable<Item> {
/** 栈顶元素 */
private Node first;
/** 栈元素数量 */
private int N;
/** 通过内部类定义链表节点 */
private class Node{
Item item;
Node next;
}
/**
* 向栈顶增加元素，即在链表的头插入节点
* @param item
*/
@Override
public void push(Item item) {
Node oldFirst=first;
first=new Node();
first.item=item;
first.next=oldFirst;
N++;
}
/**
* 从栈顶移除元素，即移除链表的头部节点
* @return
*/
@Override
public Item pop() {
Item item=first.item;
first=first.next;
N--;
return item;
}
@Override
public boolean isEmpty() {
return N==0;
}
@Override
public int size() {
return N;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
/**
* 支持迭代方法，实现在内部类里
*/
private class ListIterator implements Iterator<Item> {
private Node current = first;
@Override
public boolean hasNext() {
//或者 N!=0
return current !=null;
}
@Override
public Item next() {
Item item=current.item;
current=current.next;
return item;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
public static void main(String[] args) {
//测试
Stack<String> stack=new IterableLinkedListStack<>();
stack.push("aa");
stack.push("bbb");
stack.push("abc");
for (String s:(IterableLinkedListStack<String>)stack) {
System.out.println(s);
}
System.out.println("stack.size="+stack.size());
System.out.println("stack.pop="+stack.pop());
System.out.println("stack.size="+stack.size());
System.out.println("stack.isEmpty="+stack.isEmpty());
System.out.println("stack.pop="+stack.pop());
System.out.println("stack.pop="+stack.pop());
System.out.println("stack.size="+stack.size());
System.out.println("stack.isEmpty="+stack.isEmpty());
//测试输出
/**
* abc
* bbb
* aa
* stack.size=3
* stack.pop=abc
* stack.size=2
* stack.isEmpty=false
* stack.pop=bbb
* stack.pop=aa
* stack.size=0
* stack.isEmpty=true
*/
}
}
使用链表实现队列
队列是一种基于先进先出(FIFO)策略的集合模型。
下面基于链表实现队列，并演示使用。
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.queue;
/**
* 队列
* @author ijiangtao.net
* @param <Item>
*/
public interface Queue<Item> {
/**
* 队列是否为空
* @return
*/
boolean isEmpty();
/**
* 队列大小
* @return
*/
int size();
/**
* 入队
* @param item
*/
public void enqueue(Item item);
/**
* 出队
* @return
*/
public Item dequeue();
}
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.queue.impl;
import net.ijiangtao.tech.algorithms.algorithmall.datastructure.queue.Queue;
import java.util.Iterator;
/**
* 队列
* @author ijiangtao.net
* @param <Item>
*/
public class IterableLinkedListQueue<Item> implements Queue<Item>,Iterable<Item>{
/** 队头，最初入队的节点 */
private Node first;
/**队尾，最晚入队的节点*/
private Node last;
/** 队列中元素的数量 */
private int N;
private class Node{
Item item;
Node next;
}
@Override
public boolean isEmpty() {
//或N==0
return first==null;
}
@Override
public int size() {
return N;
}
/**
* 入队，即向队尾增加一个元素
* @param item
*/
@Override
public void enqueue(Item item) {
Node oldLast=last;
last=new Node();
last.item=item;
last.next=null;
if (isEmpty()){
first=last;
}else {
oldLast.next=last;
}
N++;
}
/**
* 出队，即移除队头元素
* @return
*/
@Override
public Item dequeue() {
Item item=first.item;
first=first.next;
if (isEmpty()){
last=null;
}
N--;
return item;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
/**
* 支持迭代方法，实现在内部类里
*/
private class ListIterator implements Iterator<Item> {
private Node current = first;
@Override
public boolean hasNext() {
//或者 N!=0
return current !=null;
}
@Override
public Item next() {
Item item=current.item;
current=current.next;
return item;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
public static void main(String[] args) {
//测试
Queue<String> queue=new IterableLinkedListQueue<>();
queue.enqueue("aa");
queue.enqueue("bbb");
queue.enqueue("abc");
for (String s:(IterableLinkedListQueue<String>)queue) {
System.out.println(s);
}
System.out.println("queue.size="+queue.size());
System.out.println("queue.dequeue="+queue.dequeue());
System.out.println("queue.size="+queue.size());
System.out.println("queue.isEmpty="+queue.isEmpty());
System.out.println("queue.dequeue="+queue.dequeue());
System.out.println("queue.dequeue="+queue.dequeue());
System.out.println("queue.size="+queue.size());
System.out.println("queue.isEmpty="+queue.isEmpty());
//测试输出
/**
* aa
* bbb
* abc
* queue.size=3
* queue.dequeue=aa
* queue.size=2
* queue.isEmpty=false
* queue.dequeue=bbb
* queue.dequeue=abc
* queue.size=0
* queue.isEmpty=true
*/
}
}
使用链表实现背包
背包是一种只支持添加不支持删除的容器，它的作用是收集元素，并遍历所收集到的元素。
包(Bag)与栈一样，遵循先进后出的策略（FILO）。
下面提供基于链表的背包实现。
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.bag;
/**
* 背包
* @author ijiangtao.net
* @param <Item>
*/
public interface Bag<Item> extends Iterable<Item>{
/**
* 向背包内加入元素
* @param item
*/
void add(Item item);
}
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.bag.impl;
import net.ijiangtao.tech.algorithms.algorithmall.datastructure.bag.Bag;
import java.util.Iterator;
public class IterableLinkedListBag<Item> implements Bag<Item> {
private Node first;
private class Node{
Item item;
Node next;
}
@Override
public void add(Item item) {
Node oldFirst=first;
first=new Node();
first.item=item;
first.next=oldFirst;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
/**
* 支持迭代方法，实现在内部类里
*/
private class ListIterator implements Iterator<Item> {
private Node current = first;
@Override
public boolean hasNext() {
//或者 N!=0
return current !=null;
}
@Override
public Item next() {
Item item=current.item;
current=current.next;
return item;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
public static void main(String[] args) {
//测试
Bag<String> bag=new IterableLinkedListBag<>();
bag.add("aa");
bag.add("bbb");
bag.add("abc");
for (String s:bag) {
System.out.println(s);
}
//测试输出
/**
* abc
* bbb
* aa
*/
}
}
