数据结构基础03——线性数据结构之链表

定义:链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表(也就是数组)快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

咸鱼:首先看名字,链-表。首先是链,指的是像链一样一个连接一个,然后是表见前面的数据结构-表。简单的说就是表的一种连接实现,所以又叫连接表(相对应的数组也叫顺序表)。

分类:

一般而言主要基于
首尾两端节点分为:不带尾节点的链表和带尾节点的链表。
基于链连接方向(单向连接如A指向B,B不指向A,双向AB相互指向)分为:单向链表,双向链表
二者可以自由组合如:带尾节点的双向链表

链表java的基本实现(Java自带的链表LinkedList双向链表)

/**
一个简单的单链表实现
*/
public class LinkedList<T>  {

    /**链表中的头节点*/
    private Node<T> head;

    private int size;

    /**
     * 向链表中添加节点
     * @param data 要插入的数据
     */
    public void add(T data){
        Node<T> node = new Node<>(data);
        //数组为空插入头节点
        if(head == null){
            head = node;
            size++;
            return;
        }
//        Node<T> tempNode = findNode(size - 2);
        Node<T> tempNode = head;
        for(int i = 0;i < size; i++){
            if(tempNode.next == null){
                break;
            }
            tempNode = tempNode.next;
        }
        tempNode.next = node;
        size++;
    }


    /**
     * 基于index下标位置找到对应的Node节点
     * @param index 下标位置
     * @return 链表中该位置节点对象,如果没有返回null
     */
    public Node<T> findNode(int index){
        if(index < 0 || index > size - 1){
            return null;
        }
        Node<T> tempNode = head;
        for(int i = 0;i < index; i++){
            tempNode = tempNode.next;
        }
        return tempNode;
    }

    /**
     * 获取指定位置节点的数据
     * @param index 下标位置
     * @return
     */
    public T get(int index){
        Node<T> node = findNode(index);
        if(node == null){
            return null;
        }
        return node.data;
    }

    /**
     * 移除指定位置的节点
     * @param index 要移除位置节点的下标
     * @return
     */
    public T remove(int index){
        if(index < 0){
            return null;
        }
        if(index == 0){
            return removeFirst();
        }
        Node<T> preNode = findNode(index - 1);
        Node<T> node = preNode.next;
        if(node == null){
            return null;
        }
        Node<T> nextNode = node.next;
        if(nextNode == null){
            //删除尾节点
            preNode.next = null;
        }else{
            preNode.next = nextNode;
        }
        size--;
        T ret = node.data;
        node = null;
        return ret;
    }

    /**
     * 删除头节点
     * @return
     */
    private T removeFirst(){
        //删除头节点
        if(head == null){
            return null;
        }
        T ret = head.data;
        head = head.next;
        size--;
        return ret;
    }

    //TODO 其他常用返回(如实现List接口)


    /**
     * 链表中的节点对象
     * @param <T>
     */
    class Node<T>{
        /**
         * 保存在节点中的具体数据
         */
        T data;
        /**
         * 指向下一个节点的链
         */
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }
}

同理双向链表在Node对象的基础添加一个属性preNode指向前面的节点,带尾节点的就在LinkedList上添加end

链表常见的基本题:

1.给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
来源:力扣(LeetCode)第2题

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}


2.反转一个单链表。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
来源:力扣(LeetCode)第206题

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

3.合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6
来源:力扣(LeetCode)第23题



class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }    
        // 将n个链表以中间为对称,合并,即合并 
        while(len>1) {
            for (int i=0; i<len/2; i++) {
                lists[i] = mergeTwoLists(lists[i], lists[len-1-i]);
            }
            len = (len+1)/2;
        }
        return lists[0];
    }
    
    // 合并两个链表
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode p = head;
        while(l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if (l1 != null) {
            p.next = l1;
        } else if (l2 != null) {
            p.next = l2;
        }
        return head.next;
    }
}
更新时间:2020-02-05 18:23:48

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/数据结构基础03线性数据结构之链表
最后更新:2020-02-05 18:23:48

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×