【数据结构Java版】链表之单链表的实现_java 单链表的实现

目录

一、ArrayList的缺陷

二、链表

（1）链表的概念及结构

（2）链表的类型

1.单向or双向

2.带头结点or不带头结点

3.循环or不循环 

 (2)单链表的实现

1.定义链表  

2.遍历链表 

3.关于链表的插入、删除操作

 三、小结

---

 一、ArrayList的缺陷

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

---

二、链表

（1）链表的概念及结构

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

 注意点:

1、链式结构在逻辑上是连续的，但是在物理上不一定连续

2、现实中的结点一般都是从堆上申请出来

3、从堆上申请的空间，是按照一定策略来分配的，两次申请的空间可以连续，可以不连续

（2）链表的类型

1.单向or双向

2.带头结点or不带头结点

3.循环or不循环 

小贴士：重点掌握两种

 1.无头单向非循环链表：

        结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。这种结构在笔试面试中出现很多。

2.无头双向链表：

        在Java的集合框架库中LinkedList底层实现就是无头双向循环链表 

---

 (2)单链表的实现

1.定义链表  

        结点（Node）：装元素的一种结构，至少包含：元素本身、指向下一个结点的线索。

        当下，我们都是使用头结点来表示一条链表Node head = null;头结点不存在，链表中一个结点都没有，链表中一个元素都没有，即链表是一条空的（empty）链表。

// 这里定义的是结点对象，不是链表对象
// 我们当前的实现中，结点对象中就两个东西，分别：元素（int）、指向下一个结点对象的线索（引用）
public class Node {
    public int val;     // 元素，类型是 int
    public Node next;   // 类型是引用，Node 类型的引用：指向一个 Node 对象
    // next：下一个
    // 当 next == null 时，代表这个结点是所在链表的最后一个结点
    
    //构造方法
    public Node(int val) {
        this.val = val;
        this.next = null;
    }
}

 2.遍历链表 

a.按照从前到后的顺序，依次访问链表中的元素 ，打印一条链表（依赖遍历链表中的所有元素）

         让 cur 指向 head 指向的对象（链表的头结点对象），当cur!=null时，表示链表中当前结点是存在的，用变量elements保存该结点的元素，打印出来，然后改变cur的指向使其指向下一个结点。cur 会经历链表中的每个结点：按照从前往后的顺序，每个结点只会经过一次。

public static void printAllElements(Node head){
    Node cur=heaad;
    while(cur!=null){
        int elements=cur.val;
        System.out.printf(elements);
        cur=cur.next;
    }
}

b.统计链表中的元素个数

        每个结点都会经过一次，所以每个元素都会经过一次，count++ 会被指向元素个数。这里使用for循环，也可以用while循环来表示。

private static int sizeOf(Node head){
    int count=0;
    for(Node cur=head;cur!=null;cur=cur.next){
        count++;
    }
    return count;
}

c.查找链表中存在的某个元素

        目前只能做到从前往后遍历，无法做到从后往前遍历（代价很大）。所谓从前到后查找，就是要遍历链表中的每个元素，和 target 进行对比。cur.val==target说明找到了，就是 cur 目前指向的结点中包含和 target 相等的元素。如果走到最后，返回一个特殊的null引用，表示没有找到。

private static Node searchElemtents(Node head ,int target){
    Node cur=head;
    while(cur!=null){
        if(cur.val==target){
            return cur;
        }
        cur=cur.next;
    }
    return null;
}

d.查找链表中所有的和某元素相等的结点

        可以用一个顺序表将所有结点保存下来。当找到符合条件的元素时就使用ArrayList中的add()添加方法，将其加入list中，最后结果返回list。

ArrayList详解：http://t.csdn.cn/dieWE

private static List<Node> searchAllNode(Node head,int target){
    List <Node> list = new ArrayList <>();
    for(Node cur = head;cur!=null;cur=cue.next){
        if(cur.val==target){
            list.add(cur);
        }
    }
    return list;
}

e.找到链表从前往后数，第n个结点（元素）的操作

1)链表中至少有 3 个结点

        要想找到第三个结点，cur需要往后走两次。如图所示 ：

private static Node findThirdNode (Node head) {
    Node cur = head;
    // 向后跳 2 步
    cur = cur.next;
    cur = cur.next;
    return cur;
}

2)链表中至少有 n 个结点

        要想找到第n个结点，cur需要往后走n-1次。

private static Node findNNode (Node head,int n) {
    Node cur = head;
    for(int i=0;i<n-1;i++){
        cur=cur.next;
    }
    return cur;
}

3)链表的长度可能小于 n

此刻 cur 可能是 null，当 cur == null 时，cur.next 就会空指针异常。所以循环条件要多一个cur!=null。

两种可能：

cur == null：说明链表的长度 < n

cur != null，说明，循环了 n - 1 次，找到了第 n 个结点

两种情况，都可以通过返回 cur 进行处理

private static Node findNNode (Node head,int n) {
    Node cur = head;
    for(int i = 0;i<n-1 && cur != null ;i++){
        cur=cur.next;
    }
    return cur;
}

f.找到链表从后往前数，第n个结点（元素）的操作

1)找到链表的倒数第1个结点

        前提条件：链表中至少有 1 个结点

        最后一个结点的特征就是它指向为空,没有下一个结点。我们就可以将其cur.next!=null作为循环条件。

private static Node findLastFirstNode(Node head) {
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        return cur;
    }

2)找到链表的倒数第2个结点

        前提条件：链表中至少有 2 个结点

        倒数第二个结点的特征就是它下一个结点的指向为空。我们就可以将其cur.next.next!=null作为循环条件。

private static Node findLastSecondNode(Node head) {
        Node cur = head;
        while (cur.next.next != null) {
            cur = cur.next;
        }
        return cur;
    }

3)找到链表的倒数第3个结点

        前提条件：链表中至少有3个结点

        同理cur.next.next.next!=null作为循环条件。

private static Node finfLastThirdNode(Node head) {
        Node cur = head;
        while (cur.next.next.next != null) {
            cur = cur.next;
        }
        return cur;
    }

3.关于链表的插入、删除操作

a.头插、头删

头插操作

1）头插元素

        先把元素装入到对应的结点中；将创建出来的新结点和链表中的结点产生关系。

private static Node headInsertionElement (Node head,int e){
    Node node=new Node(e);
    node.next=head;
    return node;
}

2）头插结点

        头插结点就是把指定结点插入单链表头部。

private static Node headInsertionNode(Node head,Node node){
    node.next=head;
    return node;
}

头删操作

        将第一个结点删除，注意链表是空的(empty)，没法删除结点，要抛出异常

ps:不理解异常操作的小朋友可以看这篇哦 http://t.csdn.cn/nRUyW

private static Node headDelete(Node head){
    if(head!=null){
        throw new RuntimeException("链表是空的，无法进行头删操作");
    }
    return head.next;
}

b.尾插、尾删

尾插操作

1）尾插元素

        把元素放入结点中；分情况处理：一是链表是一个空的链表，没有头结点；二是链表中至少有一个结点。

private static Node tailInsertElement(Node head ,int e){
    Node node=new Node(e);
    if(head==null){
        node.next==null;
        return node;
    }
    Node last=head;
    while(last.next!=null){
        last=last.next;//找最后一个结点
    }
    last.next=node;
    node.next=null;//这句话可以省略
    return head;
}

2）尾插结点

        尾插结点和尾插元素的思路是一致的，只是少了一步将元素放入新结点中。

private static Node tailInsertElement(Node head ,Node node){
    if(head==null){
        node.next==null;
        return node;
    }
    Node last=head;
    while(last.next!=null){
        last=last.next;//找最后一个结点
    }
    last.next=node;
    node.next=null;//这句话可以省略
    return head;
}

尾删操作

        尾删操作有三种情况：一是空链表；二是只有一个结点；三是至少有两个结点。对于空链表，通过抛出异常进行抱怨。只有一个结点是，可以返回null表示经过删除后，链表变为空链表了。三则需要找到倒数第二个结点，将倒数第二个结点的指向变为null。

private static Node tailDeleteNode(Node node){
    if(head==null){//空链表
        throw new RunTimeException("空链表，不能进行删除");
    }
    if(head.next==null){//只有一个结点
        return null;
    }
    Node lastOfLast=head;
    while(lastOfLast.next.next!=null){//找到倒数第二个结点
        lastOfLast=lastOfLast.next;
    }
    lastOfLast.next=null;//删除最后一个结点
    return head;
}

c.指定删除、插入

1)将e插入到到指定结点之后

        先找到的 node 的下个结点，记为 nextOfNode；再找到 node 的下一个的下一个结点，记为 nextOfNext；让 node 的 next 指向 下下个结点。

private static void insertElements(Node node,int e){
    Node newNode = new Node(e);
    newNode.next=node.next;
    node.next=newNode;
}

---

 三、小结

        无头单链表的概念和操作相较而言是比较简单的，我们需要勤加练习，理解头结点和指向关系。

        下面为大家整理了一些单链表的oj题供大家练习理解。

http://t.csdn.cn/cFe7R    206. 反转链表

http://t.csdn.cn/kivkD      203. 移除链表元素

http://t.csdn.cn/52UNu    876. 链表的中间结点

http://t.csdn.cn/Fx1XM    21. 合并两个有序链表

http://t.csdn.cn/WxzGm  链表中倒数第k个结点_牛客题霸_牛客网  

http://t.csdn.cn/MMwUC 链表分割_牛客题霸_牛客网

http://t.csdn.cn/rN6b4     链表的回文结构_牛客题霸_牛客网

---