Java集合中的链表与结构详解

2025-08-13 22:50
文章标签 链表 java 详解 集合 结构

本文主要是介绍Java集合中的链表与结构详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

《Java集合中的链表与结构详解》链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序的通过链表中的引用链接次序实现,文章对比ArrayList与LinkedList的结构差异,详细讲解了链表...

前情提要：在学习 ArrayList 时，认识到由于其底层是一段连续空间，当在 ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此 ArrayList 不适合做任意位置插入和删除比较多的场景。因此：Java 集合中又引入了LinkedList，即链表结构。

一、链表概念与结构

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

其结构总共有8种：

        带头链表中的第一个节点相当于一个标记，如果采用头插法新增节点，只能在当前头的下一个节点插入；而如果是不带头的链表，头插法是在第一个节点前面新增节点。

Java集合中的链表与结构详解

二、当向单链表的实现

整个实现将围绕下图展开：

        定义一个 cur 对象，表示当前节点。用法：遍历链表。

Java集合中的链表与结构详解

注意

1、cur 为空和 cur.next 为空的区别。     

2、单向链表不能回退。

2.1 准备工作

        1、先定义一个类用来表示整个链表，名为 SingleLinkedList。

        2、而链表中包含节点，每个节点带有两个域，一个是数据域存储整型数据；另一个是指针域，指针域中存放的是下一个 节点 的引用，因此其类型也就是节点；且注意两个属性都用 public 修饰，在测试时大有用途。将每个节点封装成链表的内部类。

        3、定义一个头部节点，用于查找或者输出链表数据，但这里并不代表链表带头。

        4、将对链表的操作封装成一个接口，其功能包括打印链表数据 display、计算链表长度 size、查找数据 contains、头插法插入数据 addFirst、尾插法插入数据 addLast、任意位置插入数据 addIndex、删除第一次出现 key 的节点 remove、删除所有值为 key 的节点 removeAllKey、清空。

SingleLinkedList 链表：

package test;
// 不带头 单向 链表
public class SingleLinkedList implements ILink{
    static class ListNode{   // 每一个 节点 都是对象，具有共同属性，因此可以抽象成内部类
        public int val;
        public ListNode next;  // 节点的地址，类型也应该是节点的类型
        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;  // 头节点
    @Override
    // ......
}

ILink 接口：

package test;
/**
 * 链表的操作
 */
public interface ILink {
    //头插法
    void addFirst(int data);
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    void addIndex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);
    //删除第一次出现关键字为key的节点
    void remove(int key);
    //删除所有值为key的节点
    void removeAllKey(int key);
    //得到单链表的长度
    int size();
    // 清空
    void clear();
    // 打印链表数据
    void display();
}

        在实现具体的操作之前，还需要考虑链表是否为空，即 head == null ?

2.2 初始化链表

        在具体实现各项功能之前，需要有一个原始的链表，利于展示操作效果。其定义方法如下

package test;
public class SingleLinkedList implements ILink{
    // ......
    public void creatList(){  // 创建一个原始链表
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        this.head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
    }
    // ......
}

2.3 打印数据、链表长度、查找数据

        这三个功能都需要将链表从头到尾遍历一遍。而遍历的条件只是当前节点不为空。

package test;
public class SingleLinkedList implements ILink{
    // ......
    @Override
    public void display() {
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();   // 换行
    }
    @Override
    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
}
package test;
public class TestSingle {
    public static void main(String[] args) {
        // ILink iLink = new SingleLinkedList(); // 通过接口无法调用 creatList()
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.creatList();  // 还没实现新增节点功能前调用的原始链表
        linkedList.display();
        System.out.println(linkedList.size());
    }
}

2.4 头插法

Java集合中的链表与结构详解

@Override
public void addFirst(int data) {
    ListNode newNode = new ListNode(data);
    newNode.next = head;
    this.head = newNode;
}

        即使原先的链表是空的，代码一样能实现头插法插入节点。

2.5 尾插法

Java集合中的链表与结构详解

@Override
public void addLast(int data) {
    ListNode newNode = new ListNode(data);
    if (head == null){  // 原来链表中一个节点都没有的情况下
        head = newNode;
        return;
    }
    ListNode cur = head;
    while (cur.next != null){
        cur = cur.next;
    }  // 循环走完说明 cur.next == null 了
    cur.next = newNode;
}
package test_8_7;
public class TestSingle {
    public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        // 实现新增节点功能之后，不需要调用 creatList()，也可以创建链表
        // 头插法
        linkedList.addFirst(11);
        linkedList.addFirst(22);
        linkedList.addFirst(33);
        linkedList.addFirst(44);
        // 尾插法
        linkedList.addLast(55);
        linkedList.display();
        System.out.println(linkedList.size());
    }
}

2.6 任意位置插入节点

注意

1、指定位置的合法性；

2、指定下标为 0 和 指定位置等于链表长度 的情况分开处理；

3、单向链表不能回退，因此注意 cur 的位置；

4、所有的插入，优先绑定后面的节点。

Java集合中的链表与结构详解

    @Override
    public void addIndex(int index, int data) throws IllegalIndexException{
        int len = this.size();  // 存储当前长度，好处：提高效率
        if (index < 0 || index > len){
            throw new IllegalIndexException("指定位置不合法！！！");
        }else {
            if (index == 0){
                this.addFirst(data);
                return;
            }
            if (index == len){
                this.addLast(data);
                return;
            }
            ListNode newNode = new ListNode(data);
            ListNode cur = head;
            while (index - 1 != 0){
                cur = cur.next;
                index--;
            }
            newNode.next = cur.next;
            cur.next = newNode;
        }
    }
package test;
// 处理指定位置的不合法异常
public class IllegalIndexException extends RuntimeException{
    public IllegalIndexException(){
    }
    public IllegalIndexException(String msg){
        super(msg);
    }
}

2.7 删除第一次出现 key 的节点

Java集合中的链表与结构详解

    @Override
    public void remove(int key) {
        if (head == null){
            return;
        }
        if(head.val == key){
            head = null;
        }
        ListNode cur = findNodeOfKey(key);
        if (cur == null){
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }
    public ListNode findNodeOfKey(int key){  // 找到存储的数据是key的对象，并返回
        ListNode cur = head;
        while (cur.next != null){
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

提示

1、在链表中查找 key 可封装成一个方法

2、查找 key 的条件 cur.next 不为空的前提下，已经判断了 cur.next 存储的数据是否等于 key 了

2.8 删除链表中所有数据为 key 的节点

Java集合中的链表与结构详解

Java集合中的链表与结构详解

Java集合中的链表与结构详解

    @Override
    public void removeAllKey(int key) {
        if (head == null){
            return;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null){
            if (cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val == key){
            head = head.next;
        }
    }

2.9 清空

        像之前“清空” ArrayList 的方法在链表中是不可行的，因为如果引用一直存在，那么引用所指的对象无法被内存回收，容易造成内存泄漏，因此只有将 next 都置空了才算清空了链表数据。

Java集合中的链表与结构详解

    @Override
    public void clear() {
        ListNode cur = this.head;
        while (cur != null){
            ListNode prev = cur.next;
            cur.next = null;
            cur = prev;
        }
        head = null;
    }

三、面试题

3.1 删除链表中等于给定值 key 的所有节点。（与上面的 2.8 一个意思）

3.2反转一个单链表。

Java集合中的链表与结构详解

    public ListNode reverseList() {  // 反转
        if(head == null){
            return null;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curNode = cur.next;
            cur.next = head;
            head = cur;
            cur = curNode;
        }
        return head;
    }

3.3返回链表中的中间节点，如果有两个中间节点，则返回第2个节点。

提示，不能通过计算链表长度的方法进行编程。

那么，采用双指针的方法，快指针走两步，慢指针走1步，最后慢指针指向的就是中间。

Java集合中的链表与结构详解

    public ListNode middleNode() {  // 找中间节点
      python  ListNode fast = head;  // 快指针，走两步
        ListNode slow = head;  // 慢指针，走一步
        while(fast != null && fast.next != null){  // &&前面必须是 fast != null 的条件
            fast = fast.next.next;
            slow = slow.next;
        }
        /*while(fast.next != null && fast != null){  // 输出 NullPointerException
            fast = fast.next.next;
            slow = slow.next;
        }*/
        return slow;
    }

3.4输出该链表中倒数第 k 个节点。

        虽然 leetcode 上已经保证了 k 的合法性，但自己实现的时候还是需要注意 k 的有效范围。

Java集合中的链表与结构详解

    public int kthToLast(int k) {  // 返回倒数第k个字节的数据
        if(head == null){
            return -1;
        }
        // 注意k的范围
        if (k <= 0){
            return -1;
        }
        /*if (k > 5){  // 这样写还得求链表的长度，不好
            return -1;
        }*/
        ListNode fast = head;
        ListNode slow = head;
        int count = 0;
        while(count != k-1){  // 为了与慢指针拉开一定的距离
            fast = fast.next;
            if(fast == null)  // 这里就是判断k是否超出链表长度的条件
                return -1;
            count++;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

3.5合并两个有序链表并按升序排序成有序链表返回。

提示

1、创建一个头节点，作为标志，可存储数据，但该数据无实际意义；

2、返回的节点不是创建的头节点。

3、在自己实现的链表中实现时，需要注意，因为该方法操作的是两个链表，因此不好将它定义到 SingleLinkedList 这个类中，因此直接定义到测试类。但直接定义到测试类时因为 ListNode 是 SingleLinkedList 的内部类，需要用 SingleLinkedList. 来调用 ListNode

Java集合中的链表与结构详解

package test;
public class TestSingle {
    public static SingleLinkedList.ListNode mergeTwoLists
            (SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB) { // 合并两个有序链表并排序
        SingleLinkedList.ListNode newHead = new SingleLinkedList.ListNode(-1); // 随便传一个数据，因为这个数据无效
        SingleLinkedList.ListNode tmp = newHead;
        while(headA != null && headB != null){
            if (headA.val < headB.val){
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }else{
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if (headA != null){
            tmp.next = headA;
        }
        if (headB != null){
            tmp.next = headB;
        }
        return newHead.next;
    }
    public static void main(String[] args) {
        // 测试合并两个链表
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addFirst(4);
        linkedList.addLast(11);
        linkedList.addLast(19);
        linkedList.addLast(44);
        SingleLinkedList linkedList2 = new SingleLinkedList();
        linkedList2.addFirst(3);
        linkedList2.addLast(6);
        linkedList2.addLast(32);
        linkedList2.addLast(57);
        SingleLinkedList.ListNode newNode = mergeTwoLiwww.chinasem.cnsts(linkedList.head, linkedList2.head);
        linkedList.display(newNode);
    }
}

3.6以 x 值为基准将链表分割成两部分，所有小于 x 的节点排在大于或等于 x 的节点之后。

Java集合中的链表与结构详解

    public ListNode partition(int x) {  // 不改变原来数据的顺序下，将所有小于x的结点排在其余结点之前
        ListNode beforeStart = null;  // 小于x的头节点
        ListNode beforeEnd = null;    // 小于x的尾节点
        ListNode afterStart = null;   // 大于x的头节点
        ListNode afterEnd = null;     // 大于x的尾节点
        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                if(beforeStart == null){  // 第一次插入
                    beforeStart = beforeEnd = cur;
                }else{
                    beforeEnd.next = cur;
                    beforeEnd = beforeEnd.next;
                }
            }else{
                if(afterStart == null){
                    afterStart = afterEnd = cur;
                }else{
                    afterEnd.next = cur;
                    afterEnd = afterEnd.next;
                }
            }
            cur = cur.next;
        }
        // 如果没有小于x的节点
        if (beforeStart == null){
            return afterStart;
        }
        // 前后两部分衔接起来
        beforeEnd.next = afterStart;
        // 第2部分的最后一个节点的引用要置空，否则编译超出范围
        if(afterStart != null){
            afterEnd.next = null;
        }
        return beforeStart;
    }

3.7判断是否为回文链表。

提示

1、找到链表的中间节点；

2、将中间节点后面的节点反转；

3、头节点的值与最后一个节点的值进行比较，然后头节点往后，最后一个节点往前。

        注意此题需要区分链表的节点数，如果是奇数比较好判断，但如果是偶数，需要考虑另一个判断条件。

奇数情况下：

Java集合中的链表与结构详解

偶数情况下：

Java集合中的链表与结构详解

判断条件是 fast.next = slow;  不能是 slow.next = fast;
且该判断条件前提是两者的数据是相等的，因此判断顺序很重要。

    public boolean chkPalindrome(){ // 判断是否是回文链表
        if(head == null){
            return true;
        }
        // 1、找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
       javascript // 2、反转
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        // 3、判断是否是回文
        while(head != slow){
            if (head.val != slow.val){
                return false;
            }
            // 如果链表是偶数的话，应该是下面的判断条件
            // 前提是两个val值是相等的
            if (head.next == slow){  // 注意是head的下一个节点是slow才对，因为slow的下一个节点回到了slow后面了。
                return true;
            }
            head = head.next;
            slandroidow = slow.next;
        }
        return true;
    }

3.8输入两个链表，找出它们的公共节点。

Java集合中的链表与结构详解

    public SingleLinkedList.ListNode getIntersectionNode
            (SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB) {  // 两链表是否相交
        SingleLinkedList.ListNode pLong = headA;  // 假设链表A的长度比链表B的长
        SingleLinkedList.ListNode pShort = headB;
        int lenA = 0;   // 链表A的长度
        int lenB = 0;   // 链表B的长度
        while (pLong != null){
            lenA++;
            pLong = pLong.next;
        }
        while (pShort != null){
            lenB++;
            pShort = pShort.next;
        }
        // 因为在计算长度时改变了两个值，因此要从新定义
        pLong = headA;
        pShort = headB;
        // 计算两个链表长度的差值
        int len = lenA - lenB;
        if (len < 0){  // 如果len为负数，说明lenB大于lenA，规定pLong一定指向长的链表
            pLong = headB;
            pShort = headA;
            len = lenB - lenA;  // 记住要把差值换成正数
        }
        // 长的链表先走len步
        while (len != 0){
            pLong = pLong.next;
            len--;
        }
        // 两个引用同时走，知道它们相遇
        while (pLong != pShort){
            pLong = pLong.next;
            pShort = pShort.next;
        }
        if (pLong == null){
            return null;  // 说明没有相交
        }
        return pLong;
    }

测试：

    public static void creatIntersect
            (SingleLinkedList.ListNode headA, SingleLinkedList.ListNode headB){  // 自己实现相交
        headA.next.next = headB.next.next.next;
    }
    public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addFirst(5);
        linkedList.addLast(1);
        linkedList.addLast(8);
        linkedList.addLast(4);
        linkedList.addLast(5);
        SingleLinkedList linkedList2 = new SingleLinkedList();
        linkedList2.addFirst(4);
        linkedList2.addLast(1);
        linkedList2.addLast(6);
        linkedList2.addLast(8);
        linkedList2.addLast(4);
        linkedList2.addLast(5);
        creatIntersect(linkedList.head, linkedList2.head);
        SingleLinkedList.ListNode ret = getIntersectionNode(linkedList.head, linkedList2.head);
        System.out.println(ret.val);
    }

3.9判断链表中是否有环。* 进阶：给javascript定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

Java集合中的链表与结构详解

Java集合中的链表与结构详解

    public boolean hasCycle(){  // 判断当前链表是否有环
        if (head == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }
    public void creatLoop(){  // 创建环
        ListNode cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = head.next.next.next;
    }
    public ListNode detectCycle() {   // 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
        ListNode fast = head;
        ListNode slow = head;
        while( fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null){
            return null;  // 说明没有环
        }
        slow = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

测试类：

public class TestSingle {
    public static void main(String[] args) {
        // 测试返回链表开始入环的第一个节点。
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addFirst(5);
        linkedList.addLast(1);
        linkedList.addLast(8);
        linkedList.addLast(4);
        linkedList.addLast(5);
        linkedList.creatLoop();
        System.out.println(linkedList.hasCycle());
        SingleLinkedList.ListNode ret = linkedList.detectCycle();
        System.out.println(ret.val);
    }
}

到此这篇关于Java集合中的链表与结构详解的文章就介绍到这了,更多相关java集合链表内容请搜索China编程(www.chinasem.cn)以前的文章或继续浏览下面的相关文章希望大家以后多多支持China编程(www.chinasem.cn)！

这篇关于Java集合中的链表与结构详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1155716。

相关文章

Linux查询服务器 IP 地址的命令详解

Linux查询服务器 IP 地址的命令详解

《Linux查询服务器IP地址的命令详解》在服务器管理和网络运维中,快速准确地获取服务器的IP地址是一项基本但至关重要的技能,下面我们来看看Linux中查询服务器IP的相关命令使用吧... 目录一、hostname 命令：简单高效的 IP 查询工具命令详解实际应用技巧注意事项二、ip 命令：新一代网络配置全
阅读更多...
Java异常捕获及处理方式详解

Java异常捕获及处理方式详解

《Java异常捕获及处理方式详解》异常处理是Java编程中非常重要的一部分,它允许我们在程序运行时捕获并处理错误或不预期的行为,而不是让程序直接崩溃,本文将介绍Java中如何捕获异常,以及常用的异常处... 目录前言什么是异常？Java异常的基本语法解释：1. 捕获异常并处理示例1：捕获并处理单个异常解释：
阅读更多...
Java实现TXT文件导入功能的详细步骤

Java实现TXT文件导入功能的详细步骤

《Java实现TXT文件导入功能的详细步骤》在实际开发中,很多应用场景需要将用户上传的TXT文件进行解析,并将文件中的数据导入到数据库或其他存储系统中,本文将演示如何用Java实现一个基本的TXT文件... 目录前言1. 项目需求分析2. 示例文件格式3. 实现步骤3.1. 准备数据库（假设使用 mysql
阅读更多...
java -jar example.jar 产生的日志输出到指定文件的方法

java -jar example.jar 产生的日志输出到指定文件的方法

《java-jarexample.jar产生的日志输出到指定文件的方法》这篇文章给大家介绍java-jarexample.jar产生的日志输出到指定文件的方法,本文给大家介绍的非常详细,对大家的... 目录怎么让 Java -jar example.jar 产生的日志输出到指定文件一、方法1：使用重定向1、
阅读更多...
Java报错:org.springframework.beans.factory.BeanCreationException的五种解决方法

Java报错:org.springframework.beans.factory.BeanCreationException的五种解决方法

《Java报错:org.springframework.beans.factory.BeanCreationException的五种解决方法》本文解析Spring框架中BeanCreationExce... 目录引言一、问题描述1.1 报错示例假设我们有一个简单的Java类，代表一个用户信息的实体类：然后，
阅读更多...
从基础到高阶详解Python多态实战应用指南

从基础到高阶详解Python多态实战应用指南

《从基础到高阶详解Python多态实战应用指南》这篇文章主要从基础到高阶为大家详细介绍Python中多态的相关应用与技巧,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、多态的本质：python的“鸭子类型”哲学二、多态的三大实战场景场景1：数据处理管道——统一处理不同数据格式
阅读更多...
SpringBoot集成P6Spy的实现示例

SpringBoot集成P6Spy的实现示例

《SpringBoot集成P6Spy的实现示例》本文主要介绍了SpringBoot集成P6Spy的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录本节目标P6Spy简介抛出问题集成P6Spy1. SpringBoot三板斧之加入依赖2. 修改
阅读更多...
Python学习笔记之getattr和hasattr用法示例详解

Python学习笔记之getattr和hasattr用法示例详解

《Python学习笔记之getattr和hasattr用法示例详解》在Python中,hasattr()、getattr()和setattr()是一组内置函数,用于对对象的属性进行操作和查询,这篇文章... 目录1.getattr用法详解1.1 基本作用1.2 示例1.3 原理2.hasattr用法详解2.
阅读更多...
Python开发简易网络服务器的示例详解(新手入门)

Python开发简易网络服务器的示例详解(新手入门)

《Python开发简易网络服务器的示例详解(新手入门)》网络服务器是互联网基础设施的核心组件,它本质上是一个持续运行的程序,负责监听特定端口,本文将使用Python开发一个简单的网络服务器,感兴趣的小... 目录网络服务器基础概念python内置服务器模块1. HTTP服务器模块2. Socket服务器模块
阅读更多...
Python用Flask封装API及调用详解

Python用Flask封装API及调用详解

《Python用Flask封装API及调用详解》本文介绍Flask的优势（轻量、灵活、易扩展）,对比GET/POST表单/JSON请求方式,涵盖错误处理、开发建议及生产环境部署注意事项... 目录一、Flask的优势一、基础设置二、GET请求方式服务端代码客户端调用三、POST表单方式服务端代码客户端调用四
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2