数据结构之链表

链表

链表是真正的动态数据结构，最简单的动态数据结构，数据存储在“结点”（Node）中优点：是真正的动态，不需要处理固定容量的问题。缺点：丧失了随机访问的能力

链表的增删改查

/**
 * @author zqnh
 * @date 2019/8/1 on 17:54.
 */
public class LinkedList<E>
{
    private class Node
    {
        public E e;
        public Node next;

        public Node(E e, Node next)
        {
            this.e = e;
            this.next = next;
        }

        public Node(E e)
        {
            this(e, null);
        }

        public Node()
        {
            this(null, null);
        }

        @Override
        public String toString()
        {
            return e.toString();
        }
    }
        private Node dummyHead;
        private int size;
        public LinkedList()
        {
            dummyHead=new Node(null,null);
            size=0;
        }

        //获取链表中的元素的个数
        public int getSize()
        {
            return size;
        }

        //获取链表是否为空
        public boolean isEmpty()
        {
            return size==0;
        }

        //在链表的index（0-based）位置添加新的元素e
        public void add(int index,E e)
        {
            if(index<0||index>size)
                throw new IllegalArgumentException("Add failed.Illegal index.");
               Node prev = dummyHead;
                    for(int i=0;i<index-1;i++)
                        prev=prev.next;

                   prev.next = new Node(e,prev.next);
                   size++;
                
        }
        //在链表头添加新的元素e
        public void addFirst(E e)
        {
            add(0,e);
        }
        //在链表的末尾添加新的元素e
        public void addLast(E e)
        {
            add(size,e);
        }

        //获得链表的第index（0-based）个位置的元素
        //在链表中不是一个常用的操作，练习用
        public E get(int index)
        {
            if(index<0||index>=size)
                throw new IllegalArgumentException("Get failed,Illegal index.");

            Node cur = dummyHead.next;
            for(int i=0;i<index;i++)
                cur=cur.next;
            return cur.e;
        }
        //获得链表的第一个元素
        public E getFirst()
        {
            return get(0);
        }
        //获得链表的最后一个元素
        public E getLast()
        {
            return get(size-1);
        }
        //修改链表的第index（0-based）个位置的元素为e
        //在链表中不是一个常用的操作，练习用
        public void set(int index,E e)
        {
            if(index<0||index>=size)
                throw new IllegalArgumentException("Set failed,Illegal index.");
            Node cur = dummyHead.next;
            for(int i=0;i<index;i++)
                cur = cur.next;
            cur.e = e;
        }
        //查找链表中是否有元素e
        public boolean contain(E e)
        {
            Node cur = dummyHead.next;
            while(cur != null)
            {
                if(cur.e.equals(e))
                    return true;
                cur = cur.next;
            }
            return false;
        }
        //从链表中删除index（0-based）位置的元素，返回删除的元素
        public E remove(int index)
        {
            if(index<0||index>=size)
                throw new IllegalArgumentException("Remove failed,Illegal index.");
            Node prev = dummyHead;
            for(int i=0;i<index;i++)
                prev=prev.next;
            Node retNode = prev.next;
            prev.next = retNode.next;
            retNode.next = null;
            size--;
            return retNode.e;
        }
        //从链表中删除第一个元素，返回删除的元素
        public E removeFirst()
        {
            return remove(0);
        }

        //从链表中删除最后一个元素，返回删除的元素
        public E removeLast()
        {
            return remove(size-1);
        }

        @Override
        public String toString()
        {
            StringBuilder res = new StringBuilder();
            Node cur = dummyHead.next;
            while(cur != null)
            {
                res.append(cur+"->");
                cur = cur.next;
            }
           /*for(Node cur = dummyHead.next;cur!=null;cur = cur.next)
               res.append(cur+"->");*/
            res.append("NULL");
            return res.toString();
        }
}

链表的时间复杂度

添加操作	addLast O(1)	addFirst O(1)	add(index,e) O(n/2)=O(n)
删除操作	removeLast(e) O(n)	removeFirst(e) O(1)	remove(index) O(n/2)=O(n)
修改操作	set(index,e) O(n)
查找操作	O(n)	修改和查找都得遍历

链表与递归（删除链表元素）

​ 链表删除元素的过程

---

删除链表中等于给定值 val 的所有节点（leecode）。

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

public class Solution
{
    public ListNode removeElements(ListNode head, int val)
    {
        //如果是头节点
        while(head != null && head.val == val)//循环遍历当头节点不为null
        {
            ListNode delNode = head;	//将头节点赋值给delNode（待删除的结点）
            head = head.next;	//将头节点的下一个结点设为头节点
            delNode.next = null; //将待删除的结点（也就是之前的头节点）的下一个结点设为null
        }
        if(head == null)	//如果头结点为null
            return null;	//返回null
        ListNode prev = head;	//将头节点赋值给prev
        while(prev.next != null)	//如果prev的下一个结点不为null,循环
        {
            if(prev.next.val == val)	
            {
                ListNode delNode = prev.next;	//将prev的下一个结点设为待删除的结点delNode
                prev.next = delNode.next;	//将delNode的下一个结点赋值给prev的下一个结点
                delNode.next=null;	//将delNode的下一个结点设为null
                //prev.next=prev.next.next;
            }
            else
            {
                prev = prev.next;
            }
        }
        return head;
    }
}

• 使用虚拟头节点

public class Solution
{
    public ListNode removeElements(ListNode head, int val)
    {
        ListNode dummyHead = new ListNode(-1); //设置虚拟节点
        dummyHead.next=head;	//将头节点赋值给虚拟头节点的next，设置虚拟头节点
        ListNode prev = dummyHead;	//将虚拟有节点赋值给prev
        while(prev.next != null)	//循环遍历，如果prev的next不为空
        {
            if(prev.next.val == val)
            {
                prev.next=prev.next.next;	//将prev的next的next赋值给prev的next
            }
            else
            {
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }
}

public class Solution
{
    public ListNode removeElements(ListNode head, int val)
    {
        if(head == null)
            return null;
        head.next = removeElements(head.next,val);
        if(head.val == val)
            return head.next ;
        else 
            return head;
        }
    }
}

public class Solution
{
    public ListNode removeElements(ListNode head, int val)
    {
        if(head == null)
            return null;
        head.next = removeElements(head.next,val);
        return head.val == val? head.next:head;
    }
}