数据结构--单链表

链表：（单链表、双链表、循环链表）

• 优点：插入和删除效率高；空间灵活

• 缺点：不支持随机访问，查询效率较低

单链表特点：结点单向指引，即在当前结点情况下，无法知道上一结点，只可知道下一结点

---

单链表：

public class SingLinkList<T> {
    static class SingLinkListNode<T> {
        T date;
        SingLinkListNode next;

        public SingLinkListNode() {
        }

        /**
        * 初始化节点
        * @param date
        */


        public SingLinkListNode(T date) {
            this.date = date;
        }

        @Override
        public String toString() {
            return  date+"\t";
        }
    }

    SingLinkListNode<T> head;//头节点

    /**
    * 初始化头节点
    */
    public SingLinkList() {
        head = new SingLinkListNode();
    }

    /**
    * 添加元素（结点）(尾插法)
    * @param data
    */
    public void addLast(T data) {
        SingLinkListNode<T> node = new SingLinkListNode<>(data);
        SingLinkListNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }

    /**
    * 添加元素（结点）（头插法）
    * @param data
    */
    public void addFront(T data){
        SingLinkListNode<T> node = new SingLinkListNode<>(data);
        if (head.next==null){
            head.next=node;
            return;
        }
        node.next=head.next;
        head.next=node;
    }

    /**
    * 在第i个结点之前插入一个元素x，若参数错误返回false，否则插入后返回true。
    *
    * @param i
    * @return
    */
    public boolean insert(int i, T x) {
        if (i < 0 || i > getCount()) return false;
        SingLinkListNode temp = head;
        SingLinkListNode<T> node = new SingLinkListNode<T>(x);
        for (int j = 0; j < i-1; j++) {
            temp = temp.next;
        }
        node.next = temp.next;
        temp.next = node;
        return true;
    }

    /**
    * 遍历单链表
    */
    public void showLinkList() {
        if (head.next == null) return;
        SingLinkListNode temp = head;
        while (temp.next != null) {
            System.out.print(temp.next);
            temp = temp.next;
        }
        System.out.println();
    }

    /**
    * 删除值为value的元素（删除结点--单删）
    * @param value
    */
    public void del(T value) {
        SingLinkListNode temp = head;
        boolean isFlag = false;
        if (head.next == null) return;
        while (temp.next != null) {
            if (temp.next.date == value) {
                isFlag = true;
                break;
            }

            temp = temp.next;
        }
        if (isFlag) {
            temp.next = temp.next.next;
        }else {
            System.out.println("未找到该数据，删除失败！");
        }
    }

    /**
    * 删除所有值为value的数据（删除结点--多删）
    *
    * @param value
    */
    public void delAll(T value) {
        SingLinkListNode temp1 = head;
        if (head.next == null) return;
        while (temp1.next != null) {
            temp1 = temp1.next;
            if (temp1.date == value) {
                del(value);
            }
        }
    }

    /**
    * 获取节点个数
    */
    public int getCount() {
        SingLinkListNode temp = head;
        int count = 0;
        if (head.next == null) return 0;
        while (temp.next != null) {
            temp = temp.next;
            count++;
        }
        return count;
    }
}

---

应用：

有一个整数单链表L，设计一个尽可能高效的算法将所有负整数的元素移动到其他元素前面。例如，L=（1，2，-1，-2，3，-3，4），移动后 L=（-1，-2，-3，1，2，3，4）。

/**
* 将所有负整数的元素移动到其他元素前面，移动后不改变负数元素先后顺序
*
* @return
*/
public static void moveNum(SingLinkList<Integer> linkList) {
    SingLinkListNode temp = linkList.head;
    int i = 1;
    if (linkList.head.next == null) return;
    while (temp.next != null) {

        if ((Integer)temp.next.date < 0) {
            linkList.insert(i, (Integer) temp.next.date);
            i++;
            temp.next = temp.next.next;
        }else {
            temp = temp.next;
        }
    }
}
---

• 本文作者： zzr
• 本文链接： http://zzruei.github.io/2023/01482ed644.html
• 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！