数组与链表

数组

什么是数组

数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。而与它相对立的概念是非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。

面试问题:数组与链表主要区别 链表适合插入、删除,时间复杂度是O(1),而数组支持随机访问,根据下表随机访问的时间复杂度为O(1);

链表

什么是链表

数组需要连续的储存空间,而链表不需要连续的存储空间,它是通过指针将一组连续的内存块串联起来, 比如申请的是 100MB 大小的链表,不会有问题。这里把内存块称为节点,它不仅要储存数据,而且需要记录下一个节点的地址,把记录下一个节点地址称为后继指针next。 链表第一个节点称为头结点,最后一个节点称为尾节点,头结点用于记录链表的基地址,就可以遍历整个链表,而尾节点不是指向下一个节点,而是指向空地址NUll。 并且链表插入、删除时间复杂度为O(1),而随机访问时间复杂度是O(n)。

循环链表与双向链表

  • 循环链表是一种特殊的单链表。它跟单链表唯一的区别就在尾结点。单链表的尾结点指针指向空地址,表示这就是最后的结点了,但是循环链表的尾结点指针是指向链表的头结点;
  • 双向链表:单向链表只有一个方向,结点只有一个后继指针 next 指向后面的结点。而双向链表,它支持两个方向,每个结点不止有一个后继指针 next 指向后面的结点,还有一个前驱指针 prev 指向前面的结点;
  • 如果存储相同的数据,双向链表需要更多的存储空间,但它支持双向遍历,操作灵活;
  • 虽然单链表删除时间复杂度为O(1),但每次删除都需要遍历整个链表,所以时间复杂度为O(n),而双向链表已经保存前驱节点,所以遍历时间复杂度为O(1)。 Java中的LinkedHashMap就采用双向链表数据结构

数组与链表区别

  • 数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读;
  • 数组的缺点是大小固定:一经声明就要占用整块连续内存空间。如果声明的数组过大,系统可能没有足够的连续内存空间分配给它,导致内存不足出现(out of memory)。如果声明的数组过小,则可能出现不够用的情况。这时只能再申请一个更大的内存空间,把原数组拷贝进去,非常费时;
  • 链表本身没有大小的限制,并且支持动态扩容;

单链表操作

反转

方法一:递归反转法,在反转当前节点之前先反转后续节点。这样从头结点开始,层层深入直到尾结点才开始反转指针域的指向。简单的说就是从尾结点开始,逆向反转各个结点的指针域指向。

public class SimpleLinkList {
 public static void main(String[] args) {
  Node head = new Node(0);
  Node node1 = new Node(1);
  Node node2 = new Node(2);
  Node node3 = new Node(3);
  head.setNext(node1);
  node1.setNext(node2);
  node2.setNext(node3);
 
  // 打印反转前的链表,定义一个h保存head节点数据,否则打印代码执行完毕head就为空了,下面反转代码就无法执行
  Node h = head;
  while (null != h) {
   System.out.print(h.getData() + " ");
   h = h.getNext();
  }
  // 调用反转方法
  head = Reverse1(head);
  System.out.println("\n**************************");
  // 打印反转后的结果
  while (null != head) {
   System.out.print(head.getData() + " ");
   head = head.getNext();
  }
 }
 /**
  * 递归,在反转当前节点之前先反转后续节点
  */
 public static Node Reverse1(Node head) {
  // head看作是前一结点,head.getNext()是当前结点,reHead是反转后新链表的头结点
  if (head == null || head.getNext() == null) {
   return head;// 若为空链或者当前结点在尾结点,则直接返回
  }
  Node reHead = Reverse1(head.getNext());// 先反转后续节点head.getNext()
 
  head.getNext().setNext(head);// 将当前结点的指针域指向前一结点
 
  head.setNext(null);// 前一结点的指针域令为null;
 
  return reHead;// 反转后新链表的头结点
 }
}
 class Node {
 
  private int Data;// 数据域
  private Node Next;// 指针域
 
  public Node(int Data) {
   this.Data = Data;
  }
  public int getData() {
   return Data;
  }
 
  public void setData(int Data) {
   this.Data = Data;
  }
 
  public Node getNext() {
   return Next;
  }
 
  public void setNext(Node Next) {
   this.Next = Next;
  }
 }

方法二:

public static Node reverse(Node list) {
    Node curr = list, pre = null;
    while (curr != null) {
      Node next = curr.next;
      curr.next = pre;
      pre = curr;
      curr = next;
    }
    return pre;
  }

检查是否有环

例如这样的链表:A->B->C->D->B->C->D, 当遍历到节点D的时候,我们需要比较的是之前的节点A、B、C,不存在相同节点。这时候要遍历的下一个新节点是B,B之前的节点A、B、C、D中恰好也存在B,因此B出现了两次,判断出链表有环。 采取了快慢指针:

 public static boolean checkCircle(Node list){
        if(list==null) return false;
        Node fastNode=list.next;
        Node slowNode = list;
        while(fastNode!=null&&fastNode.next!=null){
            fastNode = fastNode.next.next;
            slowNode = slowNode.next;
            if(fastNode==slowNode) return true;
        }
        return false;
    }

求单链表中间节点

 public static Node findMiddleNode(Node list){
         if (list == null) return null;
 
         //fast 节点存储着list
            Node fast = list;
            Node slow = list;
 
            while (fast.next != null && fast.next.next != null) {
                //fast节点存储着fast下下节点内存地址
              fast = fast.next.next;
              slow = slow.next;
            }
 
            return slow;
    }

有序单链表合并

 public static Node mergeSortNode(Node la,Node lb){
        if(la==null) return lb;
        if(lb==null) return la;
        Node pNode = la;
        Node qNode = lb;
        Node head;
        if(pNode.data<qNode.data){
            head = pNode;
            pNode = pNode.next;
        }else {
            head = qNode;
            qNode = qNode.next;
        }
        Node rNode= head;
        while(pNode!=null&&qNode!=null){
            if(pNode.data<qNode.data){
                rNode.next = pNode;
                pNode = pNode.next;
            }else {
                rNode.next = qNode;
                qNode = qNode.next;
            }
            rNode = rNode.next;
        }
        if(pNode!=null){
            rNode.next =pNode;
        }else {
            rNode.next = qNode;
        }
        return head;
    }

删除倒数第k个节点

    public static Node deleteLastNode(Node list, int k){
        Node fast = list;
        int i=1;
        while(fast!=null&&i<k){
            fast = fast.next;
            ++i;
        }
        if(fast==null) return null;
        Node slow = list;
        Node preve = null;
        while(fast.next!=null){
            fast = fast.next;
            preve = slow;
            slow = slow.next;
        }
        if(preve==null){
            list = list.next;
        }else {
            preve.next = preve.next.next;
        }
        return list;
    }

单链表插入与删除

/**
 * 单链表插入与删除
 * @author zhangtianzhu
 *
 */
public class SingleListDemo {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        SingleListDemo sDemo = new SingleListDemo();
        Node head = null;
        //新增结点,第一个新增需要返回头指针
        head = sDemo.insertNode(1, head);
        sDemo.insertNode(2, head);
        sDemo.insertNode(3, head);
        sDemo.printListNode(head);
        System.out.println(sDemo.getNodeLength(head));
        //删除索引为2的节点
        if((head = sDemo.deleteNode(2, head))!=null){
            sDemo.printListNode(head);
        }
 
        //删除头结点
        if((head = sDemo.deleteNode(1, head))!=null){
            sDemo.printListNode(head);
        }
    }
 
    /**
     * 插入节点
     * @param data
     * @param head
     * @return
     */
    public Node insertNode(int data,Node head){
        Node node = new Node(data);
        if(head==null){
            head = node;
            return head;
        }
        Node curNode = head;
        //循环找到当前尾结点
        while(curNode.next!=null){
            curNode = curNode.next;
        }
        //尾结点指针指向新增结点
        curNode.next = node;
        return head;
    }
 
    /**
     * 单链表长度
     * @param head
     * @return
     */
    public int getNodeLength(Node head){
        Node node = head;
        int length = 0;
        while(node!=null){
            node = node.next;
            length++;
        }
        return length;
    }
    /**
     * 删除结点
     * @param index
     * @param head
     * @return
     */
    public Node deleteNode(int index,Node head){
        if(index&lt;1||index&gt;getNodeLength(head)){
            return null;
        }
        //删除头结点
        if(index==1){
            head = head.next;
            return head;
        }
        //从头结点下一个结点遍历
        Node curNode = head.next;
        //记录当前循环上一个节点用于删除结点
        Node preNode = head;
        int i = 2;
        while(curNode.next!=null){
            if(i==index){
                //删除结点,前一个结点指向当前删除的下一个结点
                preNode.next = curNode.next;
            }else {
                preNode = curNode;
                curNode = curNode.next;
            }
            i++;
        }
        return head;
    }
    public void printListNode(Node head){
        Node curNode = head;
        while(curNode!=null){
            System.out.print(curNode.getData()+&quot; &quot;);
            curNode = curNode.next;
        }
        System.out.println();
    }
 
}
 
class Node{
    int data;
    Node next = null;
    public Node(int data) {
        // TODO Auto-generated constructor stub
        this.data = data;
    }
    public int getData() {
        return data;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Android 开发艺术探索笔记二

    不管是Activity,Dialog还是Toast,它们视图都是附加在window上的,window才是view的直接管理者。

    Yif
  • 栈与队列

    当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,就可以选择栈这种数据结构。 用数组实现的栈称为顺序栈,用链表实现的栈称为链表栈 ...

    Yif
  • 线程优化

    Process中定义,值越小,优先级越高,默认是THREAD_PRIORITY_DEFAULT 0

    Yif
  • 链表倒数第n个节点

    一份执着✘
  • leetcode: 92. Reverse Linked List II

    Petrichor_
  • 20120918-双向链表类定义《数据结构与算法分析》

    将新的节点插入双向链表的时候: iterator insert(iterator itr,const Object & x)//向双向链表中插入一个x节点 { ...

    用户1154259
  • LintCode-35.翻转链表

    给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null

    悠扬前奏
  • 问题系列之Java中删除有序List的重复数据——提供两种方法

    Java学习网(www.javalearns.com)提拱 现在给出一个有序的List,删除其中重复的元素,要求第个元素只能出现一次,并且是经过的排序的; ...

    用户1289394
  • 【链表问题】打卡6:三种方法带你优雅判断回文链表

    以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。

    帅地
  • LintCode 删除排序链表中的重复数字 II题目分析代码

    给定一个排序链表,删除所有重复的元素只留下原链表中没有重复的元素。 样例 给出 1->2->3->3->4->4->5->null,返回 1->2->5->...

    desperate633

扫码关注云+社区

领取腾讯云代金券