链表

2019-01-22 本文已影响0人熊猫派

链表是一种插入和删除都比较快的数据结构，缺点是查找比较慢。内存空间是不连续的。数据集比较大，碎片化比较严重。

链表结构图：

1.png

单链表

删除图：

3.png

添加图：

4.jpeg

代码实现类

//节点类
public class LinkNode {
    public int value;
    public LinkNode next;
    public LinkNode() {
    }

    public LinkNode(int value) {
        this.value = value;
    }

    public void display(){
        System.out.print(value + "");
    }
}
//链表的封装类
public class LinkList {
    public LinkNode first;

    public LinkList() {
        this.first = new LinkNode();
    }

    /**
     * 增加操作
     * 局部变量temp为移动指针
     */
    public void insert(LinkNode linkNode) {
        //把头结点看成指针
        LinkNode temp = first;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = linkNode;
    }

    /**
     * insertNodeByIndex:在链表的指定位置插入结点。
     * 插入操作需要知道1个结点即可，当前位置的前一个结点
     * index:插入链表的位置，从1开始
     * node:插入的结点
     */
    public void insertNodeByIndex(int index, LinkNode linkNode) throws Exception {
        if (index <= 0 || index > length()+1) {
            throw new Exception("插入位置不合理");
        }
        int location = 1;
        LinkNode temp = first;
        while (first.next != null) {
            if (location++ == index) {
                linkNode.next = temp.next;
                temp.next = linkNode;
                return;
            }
            temp = temp.next;
        }
    }

    /**
     * 通过index删除指定位置的结点,跟指定位置增加结点是一样的，先找到准确位置。然后进行删除操作。
     * 删除操作需要知道1个结点即可：和当前位置的前一个结点。
     *
     * @param index：链表中的位置，从1开始
     */
    public void delNodeByIndex(int index) throws Exception {
        if (index <= 0 || index > length()) {
            throw new Exception("插入位置不合理");
        }
        LinkNode node = first;
        int location = 1;
        while (first.next != null) {
            while (node.next != null) {
                if (location++ == index) {
                    node.next = node.next.next;
                    return;
                }
                node = node.next;
            }
        }
    }


    //计算当前列表长度
    public int length() {
        int length = 0;
        LinkNode temp = first;
        while (temp.next != null) {
             temp = temp.next;
              length++;
        }
        return length;
    }
    /**
     * 遍历单链表，打印所有data
     */
    public void print(){
        LinkNode temp = first.next;
        while(temp != null){
            System.out.print(temp.value+",");
            temp = temp.next;
        }
        System.out.println();
    }
}
//测试
 public static void main(String[] args) throws Exception {
        LinkList linkList = new LinkList();
        linkList.insert(new LinkNode(1));
        linkList.insert(new LinkNode(2));
        linkList.insert(new LinkNode(3));
        linkList.print();
        System.out.print(linkList.length()+"");
        linkList.delNodeByIndex(3);
        linkList.print();
        linkList.insertNodeByIndex(4,new LinkNode(4));
        linkList.print();
    }