数据结构–链表

定义

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

优点:

• 不连续存储–>插入时间复杂度为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;
        this.size++;
    }

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);
    }
}

链表的应用

移除链表元素

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

package com.company.project.arithmetic.leetcode;
/**
 * 移除链表元素
 */
public class Solution203 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

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

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    private ListNode head;

    public Solution203() {
        head = new ListNode();
    }

    /**
     * 根据内容删除结点
     * @param head 头结点
     * @param val 目标元素
     * @return 新头结点
     */
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode preNode = dummyHead;
        while (preNode.next != null) {
            int res = preNode.next.val;
            if (res == val) {
                //删除目标结点
                ListNode delNode = preNode.next;
                preNode.next = delNode.next;
                //断开目标结点与下一结点的联系
                delNode.next = null;
            } else {
                //继续找
                preNode = preNode.next;
            }
        }
        return dummyHead.next;
    }
}

链表实现队列

package com.company.project.subject.day3;
import com.company.project.subject.day2.queue.Queue;
public class LinkedQueue<T> implements Queue<T> {
    private MyLink<T> data;

    public LinkedQueue() {
        data = new MyLink<>();
    }

    //入队
    @Override
    public void enqueue(T elem) {
        data.addTail(elem);
    }

    //出队
    @Override
    public T dequeue() {
        return data.removeHead();
    }

    //返回队首元素
    @Override
    public T getFront() {
        return data.getHead();
    }

    //返回元素数
    @Override
    public int getSize() {
        return data.getSize();
    }

    //判断队列是否为空
    @Override
    public boolean isEmpty() {
        return data.isEmpty();
    }
}

测试

package com.company.project.subject.test;
import com.company.project.subject.day2.queue.ArrayQueue;
import com.company.project.subject.day2.queue.Queue;
import com.company.project.subject.day3.LinkedQueue;

public class LinkedQueueTest {
    public static void main(String[] args) {
        int count = 100000;
        Queue<Integer> queue = new ArrayQueue<>(100);
        test(queue, count);
        Queue<Integer> linkedQueue = new LinkedQueue<>();
        test(linkedQueue,count);
        //数组队列比链表队列效率高,实现队列添加时间复杂度,数组为O(1),链表为O(n)
        //class com.company.project.subject.day2.queue.ArrayQueue总耗时: 7.353346
        //class com.company.project.subject.day3.LinkedQueue总耗时: 34.4158258
    }

    public  static void test(Queue<Integer> queue, int count ){
        long start = System.nanoTime();
        for (int i = 0; i < count; i++) {
            queue.enqueue(i+10);
        }
        while (!queue.isEmpty()){
            queue.dequeue();
        }
        long end = System.nanoTime();
        System.out.println(queue.getClass()+"总耗时: "+(end-start)/1000000000.0);
    }
}

链表实现栈

package com.company.project.subject.day3;
import com.company.project.subject.day2.stack.Stack;
public class LinkedStack<T> implements Stack<T> {
    private MyLink<T> data;
    
   public LinkedStack(){
        data = new MyLink<>();
    }
    
    @Override
    public void push(T elem) {
        data.addTail(elem);
    }

    @Override
    public T pop() {
        return data.removeTail();
    }

    @Override
    public T peek() {
        return data.getTail();
    }

    @Override
    public int getSize() {
        return data.getSize();
    }

    @Override
    public boolean isEmpty() {
        return data.isEmpty();
    }
    
     @Override
    public String toString() {
        return "LinkedStack{" +
                "data=" + data +
                '}';
    }
}

测试

package com.company.project.subject.test;

import com.company.project.subject.day3.LinkedStack;

public class LinkedStackTest {
    public static void main(String[] args) {

        LinkedStack<Integer> stack = new LinkedStack<>();
        System.out.println("栈为空?:"+stack.isEmpty());
        for (int i = 0; i < 10; i++) {
            stack.push(i);
        }
        System.out.println(stack);
        System.out.println("当前元素个数:"+stack.getSize());
    }
}