数据结构:链表《单链表》

在上一篇文章 数据结构：链表《概念》中已经介绍了什么是链表以及链表的特性是什么，废话不多说直接上干货如果实现一个单链表。

import java.util.Objects;

/**

 * @ClassName SingleLinkedNodeDemo
 * @Description 单链表
 */
public class SingleLinkedNodeDemo {


    public static void main(String[] args) {
        LinkedNode node6 = new LinkedNode(6, "A6");
        LinkedNode node1 = new LinkedNode(1, "A1");
        LinkedNode node2 = new LinkedNode(2, "A2");
        LinkedNode node5 = new LinkedNode(5, "A5");
        LinkedNode node3 = new LinkedNode(3, "A3");
        LinkedNode node4 = new LinkedNode(4, "A4");
        LinkedNode node7 = new LinkedNode(7, "A7");


        //添加节点到尾部
       /* SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLinkedNode(node6);
        singleLinkedList.addLinkedNode(node1);
        singleLinkedList.addLinkedNode(node2);
        singleLinkedList.addLinkedNode(node5);
        singleLinkedList.addLinkedNode(node3);
        singleLinkedList.addLinkedNode(node4);
        singleLinkedList.addLinkedNode(node7);
        singleLinkedList.print();*/
        System.out.println("==============================");
       //按照顺序添加节点
        SingleLinkedList singleLinkedListSort = new SingleLinkedList();
        singleLinkedListSort.addLinkedNodeBySort(node6);
        singleLinkedListSort.addLinkedNodeBySort(node1);
        singleLinkedListSort.addLinkedNodeBySort(node2);
        singleLinkedListSort.addLinkedNodeBySort(node5);
        singleLinkedListSort.addLinkedNodeBySort(node3);
        singleLinkedListSort.addLinkedNodeBySort(node4);
        singleLinkedListSort.addLinkedNodeBySort(node7);
        singleLinkedListSort.print();

        System.out.println(">>>>>>>>>>>>>>>>获取某个节点");
        LinkedNode node = singleLinkedListSort.getLinkedNodeByKey(3);
        System.out.println(node);

        singleLinkedListSort.removeLinkedNode(node4);
        System.out.println(">>>>>>>>>>>>>>>>移除节点");
        singleLinkedListSort.print();

        System.out.println(">>>>>>>>>>>>>>>>修改节点");
        singleLinkedListSort.updateLinkedNode(new LinkedNode(5, "A55555"));
        singleLinkedListSort.print();

    }


    private static class SingleLinkedList{
        //定义链表头部节点
        private LinkedNode headLinkedNode = new LinkedNode(0, null);

        /**
         * 修改节点
         * @param node
         */
        public void updateLinkedNode(LinkedNode node) {
            LinkedNode tempLinkedNode = headLinkedNode.nextNode;
            while (true) {
                if ( Objects.isNull(tempLinkedNode)) {
                    break;
                }
                if (tempLinkedNode.key == node.key) {
                    tempLinkedNode.value = node.value;
                    break;
                }
                tempLinkedNode = tempLinkedNode.nextNode;
            }
        }

        /**
         * 移除节点
         * @param node
         */
        public void removeLinkedNode(LinkedNode node) {
            LinkedNode tempLinkedNode = headLinkedNode;
            while (true) {
                if (Objects.isNull(tempLinkedNode.nextNode)) {
                    break;
                }
                if (tempLinkedNode.nextNode.key == node.key) {
                    //当前节点的KEY 等于要移除节点的KEY 把当前节点指针指向移除节点的下一个节点即可
                    tempLinkedNode.nextNode = tempLinkedNode.nextNode.nextNode;
                    break;
                }
                tempLinkedNode = tempLinkedNode.nextNode;
            }
        }

        /**
         * 根据节点KEY 获取节点信息
         * @param key
         * @return
         */
        public LinkedNode getLinkedNodeByKey(int key){
            if(Objects.isNull(headLinkedNode.nextNode)){
                return null;
            }
            LinkedNode tempLinkedNode =  headLinkedNode.nextNode;
            while (Objects.nonNull(tempLinkedNode)){
                if(key == tempLinkedNode.key){
                    return  tempLinkedNode;
                }
                tempLinkedNode = tempLinkedNode.nextNode;
            }
            return null;
        }
        /**
         * 按照顺序添加节点
         * @param node
         */
        public void addLinkedNodeBySort(LinkedNode node){
            LinkedNode tempLinkedNode = headLinkedNode;
            while (true){
                //判断头部是否有数据，头部为空直接添加进来
                if(Objects.isNull(tempLinkedNode.getNextNode())){
                    tempLinkedNode.nextNode= node;
                    break;
                }
                //如果头部指向的节点不为空，判断头部指向的节点的KEY 是否大于要添加进来节点的KEY
                //如果头部指向的节点KEY大于添加进来的节点的KEY，把头部的节点放入添加进来的节点指向的节点中，再把添加进来的节点放入头部节点
                else if (tempLinkedNode.getNextNode().key>node.getKey()) {
                    node.nextNode = tempLinkedNode.nextNode;
                    tempLinkedNode.nextNode = node;
                    break;
                }
                tempLinkedNode = tempLinkedNode.nextNode;
            }
        }

        /**
         * 添加节点到尾部
         * @param node
         */
        public void addLinkedNode(LinkedNode node){
            LinkedNode tempLinkedNode = headLinkedNode;
            while (true){
                //判断头部是否有数据，头部为空直接添加进来
                if(Objects.isNull(tempLinkedNode.getNextNode())){
                    tempLinkedNode.nextNode= node;
                    break;
                }
                tempLinkedNode = tempLinkedNode.nextNode;

            }
        }

        /**
         * 打印链表节点的数据
         */
        public void print() {
            LinkedNode temp = headLinkedNode.nextNode;
            while (temp != null) {
                System.out.println(temp.toString());
                temp = temp.nextNode;
            }
        }
    }

    private static class LinkedNode{
        private int key;
        private String value;
        private LinkedNode nextNode;

        public LinkedNode(int key, String value) {
            this.key = key;
            this.value = value;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public String getValue() {
            return value;
        }

        public void setValue(String value) {
            this.value = value;
        }

        public LinkedNode getNextNode() {
            return nextNode;
        }

        public void setNextNode(LinkedNode nextNode) {
            this.nextNode = nextNode;
        }

        @Override
        public String toString() {
            return "LinkedNode{" +
                    "key=" + key +
                    ", value='" + value + '\'' +
                    '}';
        }
    }
}

推荐文章

数据结构：哈希表《概念》 数据结构：哈希表 数据结构：链表《双链表》 数据结构：链表《单链表》 数据结构：链表《概念》