[数据结构]什么是链表?

墨蓝 2021-12-10 00:21 290阅读 0赞

> 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的–百度百科

大致分为单链表和双向链表  
1.单链表:每个节点包含两部分,一部分存放数据变量的data,另一部分是指向下一节点的next指针  
2.双向链表:除了包含单链表的部分,还增加的pre前一个节点的指针

链表的优点在于,不需要连续的存储单元,修改链表的复杂度为O(1) (在不考虑查找时)  
但是缺点也很明显:无法直接找到指定节点,只能从头节点一步一步寻找复杂度为O(n)

下面是自己实现的链表操作

public class MyNode {
        private Node headNode;
        private Node lastNode;
        private int size;
    
        public void insert(int index , int data) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException();
            }
            Node node = new Node(data);
            if (0 == size) {
                headNode = node;
                lastNode = node;
            }else if (0 == index) {
                //头节点插入
                node.next = headNode;
                headNode = node;
            }else if (size == index) {
                //尾节点插入
                lastNode.next = node;
                lastNode = node;
            }else {
                Node preNode = get(index-1);
                Node nextNode = preNode.next;
                preNode.next = node;
                node.next = nextNode;
            }
            size++;
        }
        public Node get(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException();
            }
            Node temp = headNode;
            for (int i = 0;i < index; i++) {
                temp = temp.next;
            }
            return temp;
        }
    
        public Node delete(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException();
            }
            Node deleteNode = null;
            if (0 == index) {
                //删除头结点
                deleteNode = headNode;
                headNode = headNode;
            }else if (index == size - 1) {
                //删除尾节点
                Node preNode = get(index - 1);
                deleteNode = lastNode;
                preNode.next = null;
                lastNode = preNode;
            }else {
                Node preNode = get(index - 1);
                deleteNode = preNode.next;
                preNode.next = preNode.next.next;
            }
            size--;
            return deleteNode;
        }
    
        public void outPut() {
            Node temp = headNode;
            while (null != temp) {
                System.out.println(temp.data);
                temp = temp.next;
            }
        }
    
        public static void main(String[] args) {
            MyNode myNode = new MyNode();
            myNode.insert(0,1);
            myNode.insert(1,2);
            myNode.insert(2,3);
            myNode.insert(3,4);
            myNode.insert(4,5);
            myNode.delete(2);
            myNode.outPut();
        }
    }