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

╰+哭是因爲堅強的太久メ 2021-09-20 00:50 252阅读 0赞

## 数据结构中的单向链表 ##

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 */
        }
    
    
    }
    
    复制代码

转载于:https://juejin.im/post/5c682339518825790c5b027a