[数据结构与算法]数据结构--链表

数据结构–链表

定义

链表是一种线性表,但是不像数组一样连续存储,而是将每组数据存储一个结点中,每个结点中又有着指向下一个结点的指针

优点:

• 不连续存储–>插入时间复杂度为O(1)

• 动态数据结构,不用处理固定容量的问题(栈/队列/动态数组,都是依靠数组的扩容)

缺点:

• 访问时间复杂度为O(n)

• 不能随机访问,没有索引

• 增加了结点的指针域,空间开销大

实现

我们自定义一个链表

public class MyLink<T> {}

结点

首先链表要有结点,结点中有指针域和数据域,我们定义一个结点类

private class Node {
        //数据内容
        private T value;
        //指向下一节点的引用
        private Node next;

        public Node(T value) {
            this.value = value;
            //初始化结点为空
            this.next = null;
        }

        @Override
        public String toString() {
            return value.toString();
        }
    }

链表的基本属性和方法

	//头结点
    private Node head;
    //链表中的结点个数
    private int size;

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

    //判断链表是否为空
    public boolean isEmpty() {
        return this.size == 0;
    }

    //返回链表中结点个数
    public int getSize() {
        return this.size;
    }

	@Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        //从头结点开始遍历
        Node cur = head;
        while (cur != null && cur.next != null) {
            sb.append(cur + "->");
            //追加一次结点内容,更新当前结点
            cur = cur.next;
        }

        return sb.toString();
    }

增

add()1.0

	//任意位置添加结点
    public void add(int index, T value) {
        //判断索引是否合法
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("要添加的位置不合法");
        }

        Node node = new Node(value);
        if (head == null) {
            head = node;
            this.size++;
            return;
        }
        //针对头结点做处理,原因是head没有头结点
        if (index == 0) {
            node.next = head;
            head = node;
            this.size++;
            return;
        }

        Node pre = head;
        //寻找待插入结点的前一个结点
        for (int i = 0; i < index - 1; i++) {
            pre = pre.next;
        }
        //插入结点
        node.next = pre.next;
        pre.next = node;
        this.size++;
    }

	//尾部添加结点
    public void addTail(T value) {
         //添加之前先创建新结点
         Node node = new Node(value);
         if (head == null) {
         head = node;
         } else {
         //用头结点表示当前结点
         Node curNode = head;
         //查找该链表的当前尾节点
         while (curNode.next != null) {
         curNode = curNode.next;
         }
         //添加结点(当前结点为尾结点,下一结点为新添加结点)
         curNode.next = node;
         }
         this.size++;
    }

    //头部添加结点
    public void addHead(T value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
    }

add()2.0,增加了虚拟头结点,使得每一个结点都有其前驱结点

	//任意位置添加结点
    public void add(int index, T value) {
        //判断索引是否合法
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("要添加的位置不合法");
        }

        //添加虚拟头结点
        Node dummyHead = new Node(null);
        dummyHead.next = head;
        //记录待插入的结点
        Node node = new Node(value);
        //记录带插入结点的前驱结点
        Node preNode = dummyHead;
        for (int i = 0; i < index; i++) {
            preNode = preNode.next;
        }
        //插入结点
        node.next = preNode.next;
        preNode.next = node;
        //更新头结点
        head = dummyHead.next;
        this.size++;
    }

	//尾部添加结点
    public void addTail(T value) {
        this.add(this.size, value);
    }

    //头部添加结点
    public void addHead(T value) {
        this.add(0, value);
    }

删

remove()1.0

	public T remove(int index) {
        //判断索引是否合法
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index不合法");
        }

        T res = null;
        //处理索引为0情况
        if (index == 0) {
            res = head.value;
            head = head.next;
            this.size--;
        } else {
            //pre为待删除结点的前一结点
            Node pre = head;
            for (int i = 0; i < index - 1; i++) {
                pre = pre.next;
            }
            res = pre.next.value;
            pre.next = pre.next.next;
            this.size--;
        }
        return res;
    }

	//删除头结点
    public T removeHead() {
        //记录头结点的内容
        T res = null;
        if(head == null){
            return res;
        }
        res = head.value;
        //头结点后移
        head = head.next;
        this.size--;
        return res;
    }

    //删除尾结点
    public T removeTail() {
        T res = null;
        //1,头结点为空
        if(head == null){
            return res;
        }
        //2,一个结点(头结点=尾结点)
        if(this.size==1){
            this.size--;
            res = head.value;
            head = null;
        }else{
            //3,多个结点
            Node pre = head;
            for (int i = 0; i < this.size-2; i++) {
                pre = pre.next;
            }
            res = pre.next.value;
            this.size--;
        }
        return res;
    }

remove()2.0

	public T remove(int index) {
        //判断索引是否合法
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index不合法");
        }

        //虚拟头结点,如此每个结点都有前驱结点
        Node dummyHead = new Node(null);
        dummyHead.next = head;

        //记录待删除结点的前驱结点
        Node pre = dummyHead;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        Node delNode = pre.next;
        //记录待删除结点的数据内容
        T res = delNode.value;
        //将待删除结点(pre.next)指向待删除结点的后继结点
        pre.next = delNode.next;
        //断开待删除结点与后继结点的联系
        delNode.next = null;
        //更新头结点
        head = dummyHead.next;
        this.size--;
        return res;
    }

	//删除头结点
    public T removeHead() {
        return remove(0);
    }

    //删除尾结点
    public T removeTail() {
        return remove(this.size - 1);
    }

改

	//修改指定结点的内容
    public void set(int index,T value){
        //判断索引是否合法
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index不合法");
        }

        Node curNode = head;
        for (int i = 0; i < index; i++) {
            curNode = curNode.next;
        }
        curNode.value = value;
    }

	//修改头结点
    public void setHead(T value){
        this.set(0, value);
    }

    //修改尾结点
    public void setTail(T value){
        this.set(this.size-2, value);
    }

查

	public boolean isContains(T v){
        Node curNode = head;
        while (curNode != null && !curNode.value.equals(v)) {
            curNode = curNode.next;
        }
        return curNode != null;
        /*1.0
        for (int i = 0; i < this.size-1; i++) {
            if(curNode.value.equals(v)){
                return true;
            }else{
                curNode = curNode.next;
            }
        }
        return false;*/
    }

测试

package com.company.project.subject.day3;
import java.util.Random;
public class MyLinkTest {
    public static void main(String[] args) {

        MyLink<Integer> myLink = new MyLink<>();
        for (int i = 0; i < 5; i++) {
            myLink.addTail(new Random().nextInt(100));
        }
        System.out.println("尾插:" + myLink);
        myLink.addHead(0);
        System.out.println("头插:" + myLink);
        myLink.add(1, 1);
        System.out.println("索引为1的位置插入:" + myLink);
        myLink.removeHead();
        System.out.println("删除头结点: " + myLink);
        myLink.remove(2);
        System.out.println("删除索引为2的结点:" + myLink);
        myLink.removeTail();
        System.out.println("删除尾结点:" + myLink);
        System.out.println("指定索引1的结点:" + myLink.get(1));
        System.out.println("查找头结点:" + myLink.getHead());
        System.out.println("查找尾结点:" + myLink.getTail());
        System.out.println("是否包含元素1:"+myLink.isContains(1));
        myLink.set(0,100 );
        System.out.println("修改索引0的结点内容为100: "+myLink);
        myLink.setTail(100);
        System.out.println("修改尾结点内容为100: "+myLink);
    }
}