Java-链表-单向链表

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

每个链表都包含多个节点,每个节点包括数据域+引用域。

  1. 数据域:存储节点含有的data
  2. 引用域:包含两个指针,指向上一个和下一个节点
链表的分类

链表方便插入和删除,但获取数据需要遍历,速度比数组慢。

单链表与数组差别:单链表的数据元素存放在内存空间的地址是不连续的,而数组的数据元素存放的地址在内存空间中是连续的,这也是为什么根据索引无法像数组那样直接就能查询到数据元素。


单向链表SinglyLinkedList

单向链表

基本操作:node的增删改查,判断某个结点是否存在与链表中

package com.joeaaa.demo06;

public class LinkedListTest {

    class Node{
        int val;
        Node next;
        public Node(int val){
            this.val = val;
        }
    }

    Node head = null, tail = null;

    public static void main(String[] args) {
        LinkedListTest list = new LinkedListTest();
        list.addNode(10);
        list.addNode(20);
        list.addNode(30);
        list.addNode(40);
        list.printLinkedList();
        list.addNodeAtStart(50);
        list.printLinkedList();
        list.removeNode();
        list.printLinkedList();
        list.removeNodeAtCertainIndex(3);
        list.printLinkedList();

    }

    /*
     * Adds node at the end of the current list
     */
    public void addNode(int val){
        if(head==null){
            Node temp = new Node(val);
            head = temp;
            tail = temp;
        }else{
            tail.next = new Node(val);
            tail = tail.next;
        }
    }

    /*
     * Adds node at the start of the current list
     */
    public void addNodeAtStart(int val){
        if(head==null){
            Node temp = new Node(val);
            head = temp;
            tail = temp;
        }else{
            Node temp = new Node(val);
            temp.next = head;
            head = temp;
        }
    }

    /*
     * Adds node at the certain index.
     */
    public void addNodeAtCertainIndex(int val, int index){
        Node temp = head;
        int count = 0;
        while(temp!=null && ++count!=index)
            temp = temp.next;
        Node node  = new Node(val);
        if (temp != null) {
            node.next = temp.next;
        }
        temp.next = node;
    }

    /*
     * Removes the last node in the given list and updates tail node
     */
    public void removeNode(){
        Node temp = head;
        while(temp.next!=null && temp.next.next!=null){
            temp = temp.next;
        }
        temp.next = null;
        tail = temp;
    }

    /*
     * Removes the first node in the given list and updates head node
     */
    public void removeNodeAtStart(){
        //The first node would become zombie and should be garbage collected after the below operation
        head = head.next;
    }

    /*
     * Removes the node at the given index in the given list and updates head node
     */
    public void removeNodeAtCertainIndex(int index){
        Node temp = head;
        int count = 0;
        while(temp!=null && ++count!=index)
            temp = temp.next;
        if (temp != null) {
            temp.val = temp.next.val;
        }
        if (temp != null) {
            temp.next = temp.next.next;
        }
    }

    /*
     * Checks if a node with the given value exist in the list, returns true or false.
     * Alternatively you can return the index too.
     */
    public boolean search(int target){
        Node temp = head;
        while(temp!= null){
            if(temp.val == target)
                return true;
        }
        return false;

    }

    /*
     * Checks if a node with the given value exist in the list, returns the index of the given value in the list.
     */
    public int searchAndReturnIndex(int target){
        Node temp = head;
        int count = 0;
        while(temp!=null){
            count++;
            if(temp.val==target) return count;
        }
        return -1;
    }

    /*
     * Prints the current list
     */
    public void printLinkedList(){
        System.out.println();
        Node temp = head;
        while(temp!=null){
            System.out.print(" "+temp.val);
            temp = temp.next;
        }
    }
}

时间复杂度 Time Complexity

  1. Addition – O(1)
  2. Addition at Index – O(n) where n is the number of elements.
  3. Removal – O(1)
  4. Removal at Index – O(n) where is the number of elements.
  5. Search – O(n) where n is the number of elements