美文网首页
算法与数据结构-链表((linked-list)-Java实现单

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

作者: 西召 | 来源:发表于2019-02-18 22:51 被阅读17次

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

    date: 2019-02-18 22:48:25

    categories:

    • tech
    • data-structure
    • linked-list

    tags: [tech,data-structure,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
             */
        }
    
    
    }
    
    

    links:

    author: ijiangtao.net


    相关文章

      网友评论

          本文标题:算法与数据结构-链表((linked-list)-Java实现单

          本文链接:https://www.haomeiwen.com/subject/ndltyqtx.html