title: 算法與數(shù)據(jù)結構-鏈表((linked-list)-Java實現(xiàn)單向鏈表
date: 2019-02-18 22:48:25
categories:
- tech
- data-structure
- linked-list
tags: [tech,data-structure,linked-list,Java]
數(shù)據(jù)結構中的單向鏈表
PASCAL語言之父筛谚、圖靈獎得主尼古拉斯·沃斯(Niklaus Wirth)曾有一句在計算機領域幾乎人盡皆知的名言：“算法+數(shù)據(jù)結構=程序”（Algorithm+Data Structures=Programs）。
數(shù)據(jù)結構指的是是計算機存儲、組織數(shù)據(jù)的方式。其中數(shù)據(jù)的邏輯結構分為線性結構和非線性結構。
線性結構是一個有序數(shù)據(jù)元素的集合，其數(shù)據(jù)元素之間的關系是一對一的關系，即除了第一個和最后一個數(shù)據(jù)元素之外临燃，其它數(shù)據(jù)元素都是首尾相接的。
最基礎的兩種表示元素集合的方式就是數(shù)組和鏈表烙心。
數(shù)組指的是有序的元素序列谬俄。其中一維數(shù)組是線性的數(shù)據(jù)結構。數(shù)組的優(yōu)點是通過索引可以訪問任意元素弃理，查找快溃论。數(shù)組的缺點是在初始化數(shù)組的時候，就要知道數(shù)組的元素數(shù)量痘昌，而且插入和刪除元素非常復雜钥勋。
鏈表就很好地解決了數(shù)組的缺點，其使用的空間大小和元素數(shù)量成正比辆苔，即不需要提供初始化的大小算灸，而且插入和刪除元素比較簡單，不會“牽一發(fā)而動全身”驻啤。鏈表的缺點是需要通過引用訪問任意元素菲驴，查找很復雜。
鏈表是一種遞歸的數(shù)據(jù)結構骑冗。一般鏈表分為單向鏈表和雙向鏈表兩種實現(xiàn)赊瞬。
單向鏈表（單鏈表先煎、線性鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的巧涧，對鏈表的訪問要通過從頭部開始薯蝎，依序往下讀取。而雙向鏈表（雙鏈表）的每個數(shù)據(jù)結點中都有兩個指針谤绳，分別指向直接后繼和直接前驅(qū)占锯。所以，從雙向鏈表中的任意一個結點開始缩筛，都可以很方便地訪問它的前驅(qū)結點和后繼結點消略。
下面通過Java語言實現(xiàn)單向鏈表，來展示鏈表的相關操作瞎抛。
Java實現(xiàn)單向鏈表
單向鏈表的每個節(jié)點只需要定義兩個屬性：當前節(jié)點的元素艺演，下一個節(jié)點。
class Node{
Item item;
Node node;
}
使用鏈表實現(xiàn)棧
棧是一種先進后出(FILO)的數(shù)據(jù)結構婿失，如果通過數(shù)組實現(xiàn)棧，則要考慮數(shù)組擴容的問題啄寡，可以通過鏈表來解決這個問題豪硅。
下面通過鏈表實現(xiàn)棧，并借此演示了在鏈表的頭部增加節(jié)點以及除鏈表頭部節(jié)點挺物。
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;
/**
* 鏈表實現(xiàn)可迭代的棧
* @param <Item>
* @author ijiangtao.net
*/
public class IterableLinkedListStack<Item> implements Stack<Item>,Iterable<Item> {
/** 棧頂元素 */
private Node first;
/** 棧元素數(shù)量 */
private int N;
/** 通過內(nèi)部類定義鏈表節(jié)點 */
private class Node{
Item item;
Node next;
}
/**
* 向棧頂增加元素懒浮，即在鏈表的頭插入節(jié)點
* @param item
*/
@Override
public void push(Item item) {
Node oldFirst=first;
first=new Node();
first.item=item;
first.next=oldFirst;
N++;
}
/**
* 從棧頂移除元素，即移除鏈表的頭部節(jié)點
* @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();
}
/**
* 支持迭代方法识藤，實現(xiàn)在內(nèi)部類里
*/
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
*/
}
}
使用鏈表實現(xiàn)隊列
隊列是一種基于先進先出(FIFO)策略的集合模型砚著。
下面基于鏈表實現(xiàn)隊列，并演示使用痴昧。
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>{
/** 隊頭稽穆，最初入隊的節(jié)點 */
private Node first;
/**隊尾，最晚入隊的節(jié)點*/
private Node last;
/** 隊列中元素的數(shù)量 */
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();
}
/**
* 支持迭代方法，實現(xiàn)在內(nèi)部類里
*/
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
*/
}
}
使用鏈表實現(xiàn)背包
背包是一種只支持添加不支持刪除的容器豪娜，它的作用是收集元素餐胀，并遍歷所收集到的元素。
包(Bag)與棧一樣瘤载，遵循先進后出的策略（FILO）否灾。
下面提供基于鏈表的背包實現(xiàn)。
package net.ijiangtao.tech.algorithms.algorithmall.datastructure.bag;
/**
* 背包
* @author ijiangtao.net
* @param <Item>
*/
public interface Bag<Item> extends Iterable<Item>{
/**
* 向背包內(nèi)加入元素
* @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();
}
/**
* 支持迭代方法鸣奔，實現(xiàn)在內(nèi)部類里
*/
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
*/
}
}
links:
author: ijiangtao.net
