链表

作者: 木山手札 | 来源:发表于2019-12-15 18:23 被阅读0次
  • 链表中表示一个节点的类
    private static class Node<E> {
        E element;
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }

element表示节点的值,next表示当前节点的下一个节点

  • 全局变量
    private int size;
    private Node<E> first;

size表示链表的长度,first表示链表的头节点

  • 获取索引节点
    private Node<E> node(int index) {
        checkRange(index);
        Node node = first;
        for (int i = 0; i < index; i++) {
            node = first.next;
        }
        return node;
    }

从头节点遍历获取到index节点,返回index节点的node

  • 修改index节点的值
    public E set(int index, E element) {
        Node<E> node = node(index);
        E oldValue = node.element;
        node.element = element;
        return oldValue;
    }

先获取index节点的node,然后修改node.element

  • 添加节点
    public void add(int index, E element) {
        checkRangeForAdd(index);
        if (index == 0) {
            first = new Node<E>(element, first);
        } else {
            Node<E> prev = node(index - 1);
            prev.next = new Node<E>(element, prev.next);
        }
        size++;
    }

index=0表示添加头节点,直接初始化first
在指定index位置添加节点,就是在index-1和index+1中间位置添加element,index-1.next=index.next=index+1.next

  • 删除索引位置节点
    public E remove(int index) {
        Node<E> node = first;
        if (index == 0) {
            first = first.next;
        } else {
            Node prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;// prev.next = prev.next.next;
        }
        return node.element;
    }

index=0表示删除头节点,让first.next等于first
index非0,先获取index-1节点的位置(index的前驱),让(index-1).next=index.next前驱节点.next=后继节点,代码node = prev.nextnode就是index节点

  • 获取index位置元素
   public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element.equals(null)) return i;
                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (element.equals(node.element)) return i;
                node = node.next;
            }
        }
        return -1;
    }

从first节点开始便利到size,进行equals()判断

  • index校验
    private void checkRangeForAdd(int index) {
        if (index < 0 || index > index) {
            indexOutOfBoundException(index);
        }
    }

    private void checkRange(int index) {
        if (index < 0 || index >= index) {
            indexOutOfBoundException(index);
        }
    }
  • 遍历链表
       Node node = first;
        for (int i = 0; i < size; i++) {
            node = node.next;
        }

从first开始for编列到size

       Node node = first;
       while (node != null) {
            node = node.next;
        }

从first开始遍历,只有first.next!=null就一直while()

  • 反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newHead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }

        return newHead;
    }
  • 判断是否环形链表
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) return true;
        }
        return false;
    }
  • 删除链表中的节点
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

相关文章

  • 链表基础

    链表基础 链表长度 链表为空 链表结构 链表增加

  • 双向链表&双向循环链表

    链表分为:单链表、单向循环链表、双向链表、双向循环链表本节主要说明:双向链表、双向循环链表 定义结点 一、双向链表...

  • 算法与数据结构:链表

    链表 链表还分为单向链表和双向链表, 但是这篇文章只说单向链表 , 下次再讲双向链表 . 链表和数组的区别 ? 链...

  • 链表

    链表 单链表反转链表中环的检测两个有序链表合并删除链表倒数第n个节点求链表的元素总个数 一.单向链表 链表共有特征...

  • 五、双向链表

    双向链表 此前介绍的链表,也叫做单向链表使用双向链表可以提升链表的综合性能 修改之前的单链表的源码: 双向链表 –...

  • 链表

    内容 链表数据结构 向链表添加元素 从链表移除元素 使用 LinkedList 表 双向链表 循环链表 链表数据结...

  • 数据与算法结构

    线性表 顺序表 链表(物理上离散,逻辑上连续) 链表的类别 单链表 循环链表 双链表 链表的操作 顺序表与链表的比...

  • 数据结构——链表

    本文所讲的链表是单链表,链表采用无头链表 科普下:一般链表可以分为有头节点的链表与无头节点的链表 有头节点的链表:...

  • 链表

    文章结构 链表的定义 链表的插入和删除操作 链表的特性 常见的链表结构 自定义链表 链表的经典操作 使用链表实现L...

  • Algorithm小白入门 -- 单链表

    单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表 单链表节点的结构如下: 1.1 递归反转整个单链表...

网友评论

      本文标题:链表

      本文链接:https://www.haomeiwen.com/subject/zzclnctx.html