阅读 197

算法与数据结构-链表(linked-list)-Java实现单向链表

数据结构中的单向链表

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
         */
    }


}

复制代码