链表(Java)实现

代码如下

/**
 * 单链表实现
 * @param <T>
 */
public class SinglyLinkedList<T extends Comparable<? super T>> {

    private Node<T> head;          //  指向链表头结点
    private Node<T> tail;          //  指向链表尾结点
    private int size;              //  链表长度

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头部添加元素
     *
     * @param val
     */
    public void addFirst(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            new_node.next = head;
            head = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 向链表尾部添加元素
     *
     * @param val
     */
    public void addLast(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            tail.next = new_node;
            tail = tail.next;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 有序添加元素(自定义升序排序)
     *
     * @param val
     */
    public void add(T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (!isEmpty()) {
            if (this.tail.item.compareTo(new_node.item) <= 0) {
                tail.next = new_node;
                tail = tail.next;
            } else {
                Node<T> p_node = this.head;
                Node<T> q_node = p_node;
                while (p_node != null) {
                    if (new_node.item.compareTo(p_node.item) < 0) {
                        break;
                    }
                    q_node = p_node;
                    p_node = p_node.next;
                }
                new_node.next = p_node;
                q_node.next = new_node;
            }
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 插入指定位置
     *
     * @param index
     * @param val
     */
    public void insert(int index, T val) {
        Node<T> new_node = new Node<T>(val, null);
        if (isEmpty()) {
            head = new_node;
        } else {
            if (index > size + 1) {
                System.out.println("下标超限");
            } else {
                Node<T> pre = findIndex(index - 1);
                new_node.next = pre.next;
                pre.next = new_node;
            }
        }
        size++;
    }

    /**
     * 查找指定位置的结点
     *
     * @param index
     * @return
     */
    public Node<T> findIndex(int index) {
        int i = 1;
        Node<T> p = head;
        while (p != null) {
            if (i == index) {
                return p;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    /**
     * 寻找链表中指定结点
     *
     * @param val
     * @return
     */
    public Node<T> find(T val) {
        Node<T> x = this.head;
        Node<T> t = new Node<T>(val, null);
        while (x != null) {
            if (x.item.compareTo(t.item) == 0) {
                return x;
            }
            x = x.next;
        }
        return null;
    }

    /**
     * 判断链表中是否含有指定的Val
     *
     * @param val
     * @return
     */
    public boolean containsVal(T val) {
        Node<T> p_node = this.head;
        Node<T> q_node = new Node<T>(val, null);
        while (p_node != null) {
            if (p_node.item.compareTo(q_node.item) == 0) {
                return true;
            }
            p_node = p_node.next;
        }
        return false;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 反转后的头指针
     */
    public Node<T> reverseList(Node<T> head) {
        Node<T> new_head = null;
        while (head != null) {
            Node<T> p = head.next;
            head.next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }

    /**
     * 删除链表中重复元素
     *
     * @return 删除重复元素后的头指针
     */
    public Node<T> deleteDuplicates() {
        Node<T> current = this.head;
        while (current != null && current.next != null) {
            if (current.item.compareTo(current.next.item) == 0) {
                current.next = current.next.next;
                size--;
            } else {
                current = current.next;
            }
        }
        return head;
    }

    /**
     * 删除链表中指定元素
     *
     * @param head
     * @param val
     * @return
     */
    public void remove(T val) {
        Node<T> dummyNode = new Node<T>(val, null);
        dummyNode.next = head;
        Node<T> prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.item == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
    }

    /**
     * 合并两个有序链表(迭代)
     *
     * @param l1
     * @param l2
     * @return 合并后的头结点
     */
    public Node<T> mergeTwoLists(Node<T> l1, Node<T> l2) {
        Node<T> prehead = new Node<T>();
        Node<T> prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.item.compareTo(l2.item) <= 0) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }

    /**
     * 将链表以数组的形式返回
     *
     * @return
     */
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node<T> x = head; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    /**
     * 判断链表是否为空
     *
     * @return head == null
     */
    private boolean isEmpty() {
        return this.head == null;
    }

    public Node<T> getHead() {
        return head;
    }

    public Node<T> getTail() {
        return tail;
    }

    public int getsize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node<T> p_node = this.head;
        while (p_node != null) {
            sb.append(p_node.item + " ");
            p_node = p_node.next;
        }
        return sb.toString();
    }
    
    public void Print(){
        Node<T> p = this.head;
        while(p != null){
            System.out.println(p.item);
            p = p.next;
        }
    }
    
}

本文由 罗罗 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.lwjppz.cn /archives/20190824142356
最后更新于:2020-02-09 11:55:16

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×