美文网首页
数据结构(一):数组与链表

数据结构(一):数组与链表

作者: LY丶Smile | 来源:发表于2019-08-28 07:06 被阅读0次

最近打算重新从基础开始学习,本文是学习过程中的笔记,如有错误请指正~

一、理论知识

数组与链表都是数据结构中最简单的线性结构,是数据存储的物理结构,很多别的数据结构都是从数组和链表衍生出来的,比如栈、队列、哈希表等

1. 数组(Array)

定义

有限相同类型的变量组成的有序集合

存储

  • 有限:数组的长度在创建时就已经确定了,所以如果操作不当很容易出现数组越界问题
  • 有序:数组在内存中是顺序存储的,并且元素之间是紧密排列的,中间不会出现空余的内存块,所以数组的插入、删除都需要靠移动元素来腾出空间给新元素安家。

读取

  • 数组中的每个元素都有下标(从0开始),可以按照元素的下标读取元素(随机读取),读取的效率比较高

从上面可以看出来数组的优势在于能够快速定位元素,更适合读多写少的场景

2. 链表(Linked List)

定义

物理上非连续、非顺序的数据结构,由若干节点(node)所组成

  • 每个node包括存放数据的变量data和指向下一个节点的指针next
  • 第一个节点称为头节点,最后一个节点称为尾节点

存储

  • 随机存储:链表的每一个节点分布在内存的不同位置,依靠next指针关联。可以很灵活有效地利用零散的碎片空间
  • 理论上无限:只要内存空间允许,能够插入链表的元素是无穷无尽的,不需要考虑扩容问题

读取

  • 因为存储的随机性,所以只能根据节点next指针一个个找,从头节点开始向后一个一个节点逐一查找

从上面可以看出链表的优势在于能够灵活地进行插入和删除操作,如果需要在尾部频繁插入、删除元素,用链表更适合

二、源码

  • 数组长度是有限的,所以插入新元素时需要判断长度是否足够长
  • 链表的插入、删除其实就是刷next指针

数组

/**
 * 数组
 * @author yangjunqiang
 *
 */
public class MyArrayDemo {
    
    private int[] array;
    private int size;
    
    public static void main(String[] args) {
        MyArrayDemo myArrayDemo = new MyArrayDemo(10);
        myArrayDemo.insert(1, 0);
        myArrayDemo.insert(3, 1);
        myArrayDemo.insert(5, 2);
        myArrayDemo.insert(7, 3);
        myArrayDemo.insert(9, 1);
        myArrayDemo.printf();
    }
    
    // 初始化数组,并指定大小
    public MyArrayDemo(int capacity) {
        this.array = new int[capacity];
        size = 0;
    }
    
    public void insert(int element, int index) {
        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出数组长度");
        }
        
        if(size >= array.length) {
            resize();
        }
        
        // 从右到左,将元素后移一位
        for(int i = size - 1; i > index; i--) {
            System.out.println("i = " + i + " = " + array[i]);
            array[i+1] = array[i];
        }
        
        array[index] = element;
        size++;
    }
    
    /**
     * 数组扩容
     */
    public void resize() {
        // 每次扩容,都是原数组大小的两倍
        int[] newArray = new int[array.length * 2];
        // 扩容的原理就是将旧数组的元素copy到新的数组里
        System.arraycopy(array, 0, newArray, 0, array.length);
        array = newArray;
    }
    
    public void update(int element, int index) {
        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出数组长度");
        }
        array[index] = element;
    }
    
    
    /**
     * 移除元素
     * @param index
     */
    public int remove(int index) {
        // 下标从0开始,所以index最大是size-1
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出数组长度");
        }
        
        int deletedElement = array[index];
        
        // 从左到右,挨个将元素前移一位
        for(int i = index; i < size -1; i++) {
            array[i] = array[i+1];
        }
        size--;
        return deletedElement;
    }
    
    public void printf() {
        for(int i = 0; i < size; i++) {
            System.out.println(array[i]);
        }
    }

}

链表

/**
 * 链表
 * 链表元素的定位全靠next指针
 * 链表的优势在于能够灵活地插入、删除,但是查找效率低于数组
 * 如果内存是无限的,那么链表也将是无限的
 * @author yangjunqiang
 *
 */
public class MyLinkedList {

 // 头节点
    private Node head;
    // 尾节点
    private Node last;
    private int size;
    
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.insert(1, 0);
        myLinkedList.insert(3, 1);
        myLinkedList.insert(5, 2);
        myLinkedList.insert(7, 3);
        myLinkedList.insert(9, 4);
        myLinkedList.output();
    }
    
    /**
     * 查找元素
     * @param index 位置
     * @return
     */
    public Node get(int index) {
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        Node temp = head;
        
        // 链表的查找,只能挨个查找,因为链表的每个节点只保存了数据和next指针
        for(int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
        
    }
    
    /**
     * 插入元素
     * @param data 数组
     * @param index 要插入到的位置
     */
    public void insert(int data, int index) {

        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        // 待插入的节点
        Node insertNode = new Node(data);

        // 空链表,插入后也只有一个元素
        if(size == 0) {
            head = insertNode;
            last = insertNode;
        }
        // 在头部插入,将新插入的元素next指针指向原来的head节点,把新节点变为链表的head节点
        else if(index == 0) {
            insertNode.next = head;
            head = insertNode;
        }
        // 在尾部插入,将原来的last的next指针指向新插入的元素,并将新元素置为last
        else if(size == index) {
            last.next = insertNode;
            last = insertNode;
        }
        // 在中间插入
        else {
            // 获取前一个节点的信息
            Node prevNode = get(index - 1);
            // 插入值相当于替换了prevNode,所以next指针就是prevNode的next指针
            insertNode.next = prevNode.next;
            // prevNode的next指针改为insertNode
            prevNode.next = insertNode;
        }
        size++;
    }
    
    /**
     * 移除节点
     * @param index 
     * @return
     */
    public Node remove(int index) {
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        
        Node removeNode = null;
        // 从头删除,将head的值置为它的下一个值就好
        if(index == 0) {
            removeNode = head;
            head = head.next;
        }
        // 删除最后的元素
        else if(index == size - 1) {
            Node prevNode = get(index - 1);
            removeNode = prevNode.next;
            prevNode.next = null;
            last = prevNode;
        }
        // 删除中间的元素
        else {
            // 将待删除元素的前一个元素的next指针改为待删除元素的next指针
            Node prevNode = get(index - 1);
            Node nextNode = prevNode.next.next;
            removeNode = prevNode.next;
            prevNode.next = nextNode;
        }
        size--;
        return removeNode;
    }
    
    public void output() {
        Node temp = head;
        while( temp != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }
    
}

定义Node

public class Node {

    // 存储的数据
    int data;
    // 下一个节点
    Node next;

    public Node(int data) {
        this.data = data;
    }
}

三、参考

  • 《漫画算法-小灰的算法之旅》

附件

思维导图-数组与链表

相关文章

  • 数据结构:数组

    00数据结构与算法分析:大纲01数据结构:数组02数据结构:链表03数据结构:栈03数据结构:队列 数组 数组是一...

  • 数据结构-链表

    链表与数组是个相对互补,数组不足的地方恰好用链表可以满足,它也算基础数据结构,可用来表示其他逻辑数据结构。 链表在...

  • 数据结构与算法相关

    第二章 数据结构与算法相关 1.常用的数据结构有哪些? 数组、栈、队列、链表(单链表、双向链表、循环链表)、树、散...

  • 链表(Linked List)

    什么是链表? 通过指针或者引用将一系列数据节点串起来的数据结构称为链表,链表数据结构与数组最明显的区别就是它在内存...

  • Java集合类-HashMap

    1. HashMap的数据结构 HashMap实际上是一个“链表散列”的数据结构,是数组与链表的结合体。HashM...

  • 链表

    与数组一样,链表也是一种基础的数据结构,与数组不同的是,数组需要一组连续的存储空间,但是,链表就不需要,它通过一个...

  • HashMap 1.7 和1.8区别

    一、数据结构区别 HashMap 1.7 使用数组+链表HashMap 1.8 使用Node数组+链表+红黑树(当...

  • 线性数据结构之一维数组

    线性数据结构也称为一维数据结构,包含一维数组和链表线性的数据结构强调的是存储与顺序 一维数组: 在通常编程时,我们...

  • HashMap

    元素存储: HashMap的数据结构: JDK1.7中是数组+ 单链表的数据结构。JDK1.8及之后是数组+链表+...

  • 大数据算法系列3:基本数据结构及应用

    一. 数据结构 1.1 指针的原理 1.2 链表 链表的基本操作: 链表 VS 数组:数组的长度是固定的,而且存储...

网友评论

      本文标题:数据结构(一):数组与链表

      本文链接:https://www.haomeiwen.com/subject/boksectx.html