投稿
  1. 首页
  2. java

Java 数据结构与算法 单链表的实现

code • 2022-5-5 • java • 阅读 52

Java 数据结构与算法 单链表的实现,第1张

    顺序表ArrayList的底层是数组，将数据存储在一段连续的空间上。这样，当需要在顺序表的任意位置进行插入和删除的时候，需要把部分的元素整体移动。这样做时间复杂度是O(n)，比较慢。所以顺序表不合适做任意元素的插入和删除比较频繁的场景。引进一种链表结构来解决这个问题。

一、链表的概念和结构

    链表是一种存储结构上不连续的存储结构。数据是依次通过引用来进行链接和访问的，就像一列火车这就是一种链式结构。

链表的结构，在逻辑上是连续的，但是在物理存储上是不连续的。

    对于单链表，它的结构分成了两个域，一个是数值域，用来存储数值，一个是next域，也是引用域，用来存储下一个节点的地址。要找到下一个节点，就需要next来进行访问。

    链表的结构分为单向或双向链表，带头或不带头链表，循环或不循环链表。下面的链表是一种不带头结点的非循环单向链表。主要要知道无头单链表和无头双链表。

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

单链表的实现先从简单的循环开始，到后面在进行单链表的插入和删除 *** 作。

1、定义单链表成员变量

    单链表需要数值域来保存数值，它的类型是int。又需要next域来保存下一个节点的地址，它的类型是一个引用。在定义一个ListNode类来定义这些成员变量。

class ListNode {
    //数值域
    public int val;
    //保存下一个节点地址
    public ListNode next;
    //初始化val
    public ListNode(int val) {
         this.val = val;
    }
}

    同时，为了找到这个单链表的头，要定义一个head，类型是ListNode。刚开始没有链表，不需要赋值。

public class MySingleList {

    //单链表的头节点
    public ListNode head;

}
2、打印链表display()

    假设有这样一个单链表，通过这个图，链表的下一个节点是保存在上一个节点的next域中的。要通过引用来访问下一个节点。

    如何打印链表呢？我们定义好了一个head，通过它的访问来打印链表。head.val就是这个链表的值，head.next就能够访问到下一个链表节点。

    public void display() {

    while (head != null) {
         System.out.print(head.val + " ");
         head = head.next;
    }
    System.out.println();
}

    head节点保存第一个节点的信息，所有的 *** 作都是从这个节点开始的。在这里改变了head，在其他的地方在要从head开始就不是第一个节点了。所以要使用一个临时变量cur，让cur代替head来进行 *** 作。

public void display() {
    ListNode cur = this.head;

    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();
}
3、 查找关键字key是否在链表中contains()

这个很简单，循环遍历链表，在判断每一个节点的值和要查找的值相等不相等就可以了。

public boolean contains(int key) {
    //头节点可以判断是否为空,也可以不用判断
    if (this.head == null) {
        return false;
    }

    ListNode cur = this.head;
    while (cur != null) {
        if (cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}
4、得到单链表长度size() 
public int size() {
    ListNode cur = this.head;
    int count = 0;

    while (cur != null) {
        ++count;
        cur = cur.next;
    }
    return count;
}

 下面，进行单链表的增删 *** 作

5、头插法addFirst()

    头插法就是在head节点前面在插一个节点。插入了节点后，这个节点就是一个新的头节点，要让head节点移到刚刚插入的头节点。

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

    特殊的情况是如果这个链表没有一个节点，头插法插入的节点就成了是第一次插入的节点。这个时候就直接让这个新插入的节点成为node。全部代码如下。

public void addFirst(int data) {
    ListNode node = new ListNode(data);

    //第一次插入
    if (this.head == null) {
        this.head = node;
    } else {
        //不是第一次插入
        node.next = this.head;
        this.head = node;
    }
}
6、尾插法addLast()

尾插法就是在链表的末尾插入一个节点。

    尾插要先遍历链表，找到链表的结尾，不能动head，所以在定义一个cur来寻找尾。找到后，尾结点的next域要指向新插入的节点的地址。

public void addLast(int data) {
    ListNode node = new ListNode(data);
    ListNode cur = this.head;
    while (cur.next != null) {
        cur = cur.next;
    }
    cur.next = node;
}

    特殊的，当尾插入的节点为第一次插入的时候，直接让head等于新插入的节点。尾插法全部代码如下。

public void addLast(int data) {
    ListNode node = new ListNode(data);

    if (this.head == null) {
        head = node;
    } else {
        ListNode cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
}
7、指定位置的插入addIndex()方法

    虽然单链表没有下标，但是我们指定位置插入。如图所示。按照数组的下标形式，把第一个节点下标设置为0下标。当然，你也可以从1开始。下面的代码都是基于节点从0开始的代码。

    指定位置插入要在合法的范围里面进行插入。所以要对这个范围进行判断。如果这个范围是超出了链表的范围，就要提示下标非法。先在addIndex方法里面写一个方法来判断要插入的范围是不是越界的。

    private void checkIndexAdd(int index) {
        if (index < 0 ||index > size()) {
            throw new MySingleListIndexOutOfException("越界");
        }
    }

    public void addIndex(int index, int data) {
        //1,index进行合法判断 [0, size()]
        checkIndexAdd(index);
    }

    判断完成之后，就要进行插入。返回上面的图，要在2下标插入，就要找到2下标节点的前一个0x22。找到了之后让新插入的节点的next域指向原来的2下标的节点0x33，然后让0x22的next域指向新插入的节点就可以了。

    如何找到2下标的前一个？慢慢找规律，发现，要在下标是2处插入，就要让cur走一步，要在下标是1处插入，就要让cur不要走...cur每一次走的都是要插入下标-1次。

新建立一个节点后，寻找插入位置的在addIndex中在写一个方法来实现这一步。

    private ListNode findIndexSubOne(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            --index;
        }
        return cur;
    }

    特殊的，第一个下标和最后一个下标对应得是我们的头插法和尾插法，所以直接调用就可以了。下面是全部的代码。

    private void checkIndexAdd(int index) {
        if (index < 0 ||index > size()) {
            throw new MySingleListIndexOutOfException("越界");
        }
    }

    private ListNode findIndexSubOne(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            --index;
        }
        return cur;
    }

    public void addIndex(int index, int data) {
        //1,index进行合法判断 [0, size()]
        checkIndexAdd(index);
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }

        ListNode node = new ListNode(data);
        ListNode cur = findIndexSubOne(data);
        node.next = cur.next;
        cur.next = node;
    }
8、删除第一次出现为key的值remove()

    删除第一次出现的值，需要先找到这个值的节点B的前一个节点A，然后让A指向B的下一个节点C就可以了。

如果只用一个临时节点cur来完成，那么，cur需要判断cur.next.val的值是不是要删除的值。

    特殊的，如果这个链表是空链表，那么就不需要删除。如果要删除的值在头节点或尾结点。如果是头节点，那么让head指向下一个就可以了。尾结点的话要注意不要让cur或cur.next指向null，会引起空指针异常。

    public void remove(int key) {
        //头节点删除
        if (this.head == null) {
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
        }

        //中间节点
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                ListNode del = cur.next;
                cur.next = del.next;
                return;
            }
            cur = cur.next;
        }
    }
9、删除所有为key的值removeAllKey()

    和上一个不一样的是，这个方法要求删除所有的为key的值的节点。remove方法中，删除第一次出现的值后，让cur移动了。在这个方法中，不需要移动cur。因为删除后自然cur就指向了下一个节点，如果下一个节点还是cur，直接删除，在让cur继续重复。

    //删除所有值为key的节点
    public void removeAllKey(int key) {

        if (this.head == null) {
            return;
        }
        while (this.head != null && this.head.val == key) {
            this.head = this.head.next;
        }

        ListNode cur = this.head;
        while(cur != null && cur.next != null) {
            if(cur.next.val == key) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
    }
10、全部代码 
/**
 * @author: Naion
 * @create: 2022-04-27 23:04
 * @Description:
 **/

public class MySingleList {

    static class ListNode {
        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    private ListNode head;

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

    public void addLast(int data) {
        ListNode node = new ListNode(data);

        if (this.head == null) {
            this.head = node;
            return;
        }
        ListNode cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    public void checkIndexAdd(int pos) {
        if (pos < 0 || pos > size()) {
            throw new RuntimeException("越界！");
        }
    }

    public ListNode findSubscript(int index) {
        ListNode cur = this.head;
        while (index - 1 > 0) {
            cur = cur.next;
            --index;
        }
        return cur;
    }

    public void addIndex(int index, int data) {
        checkIndexAdd(index);
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
        }
        ListNode cur = findSubscript(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public void remove(int key) {
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = this.head;
        while (cur != null && cur.next != null) {
            if (cur.next.val == key) {
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {

        if (this.head == null) {
            return;
        }
        while (this.head != null && this.head.val == key) {
            this.head = this.head.next;
        }

        ListNode cur = this.head;
        while(cur != null && cur.next != null) {
            if(cur.next.val == key) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
    }

    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            ++count;
            cur = cur.next;
        }
        return count;
    }

    public void display() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    public void clear() {
        this.head = null;
    }
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/788762.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-05-05
下一篇 2022-05-05

发表评论

登录后才能评论

评论列表（0条）

保存