链表与数组

作为线性表的两种存储方式 —— 链表和数组,这对相爱相杀的好基友有着各自的优缺点。接下来,我们梳理一下这两种方式。

链表是一种上一个元素的引用指向下一个元素的存储结构,链表通过指针来连接元素与元素;

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:**一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 **

1.单向链表

链表与数组

单向链表包含两个域,一个是信息域,一个是指针域。也就是单向链表的节点被分成两部分,一部分是保存或显示关于节点的信息,第二部分存储下一个节点的地址,而最后一个节点则指向一个空值。(上图)

public Clist()
{
    ListCountValue = 0;//初始化
    Head = null;
    Tail = null;
}

private ListNode Head;//头指针
private ListNode Tail;//尾指针
private ListNode Current;//当前指针
private int ListCountValue;//链表数据的个数

public void AddNode(int DataValue)//尾部添加数据
{
  ListNode NewNode = new ListNode(DataValue);
  if (IsNull())//如果头指针为空
  {
      Head = NewNode;
      Tail = NewNode;
  }
  else
  {
      Tail.Next = NewNode;
      NewNode.Previous = Tail;
      Tail = NewNode;
  }
  Current = NewNode;
  ListCountValue += 1;//链表数据个数加一
}

public void DeleteNode()//删除当前数据
{
    if (!IsNull())//若为空链表
    {
        if (IsBof())//若删除头
        {
            Head = Current.Next;
            Current = Head;
            ListCountValue -= 1;
            return;
        }
        if (IsEof())//若删除尾
        {
            Tail = Current.Previous;
            Current = Tail;
            ListCountValue -= 1;
            return;
        }
        Current.Previous.Next = Current.Next;//若删除中间数据
        Current = Current.Previous;
        ListCountValue -= 1;
        return;
    }
}

2.双向链表

链表与数组

每个节点有2个链接,一个是指向前一个节点(当此链接为第一个链接时,指向的是空值或空列表),另一个则指向后一个节点(当此链接为最后一个链接时,指向的是空值或空列表)。意思就是说双向链表有2个指针,一个是指向前一个节点的指针,另一个则指向后一个节点的指针。(上图)

注:循环链表就是首节点和末节点被连接在一起。循环链表中第一个节点之前就是最后一个节点,反之亦然。

数组

 int[] iArray = new int[2];

数组其实是开辟了两个空间的,在内存中,数组的名由一个对应的内存地址保存数据,然后就是开辟一段内存地址来保存数组数据, 还有一个要点就是说数组的名可以指向别的数组数据的内存地址,这样一开始的就会被垃圾回收.

在使用前需要提前申请所占内存的大小,这样不知道需要多大的空间,就预先申请可能会浪费内存空间,即数组空间利用率低

1.在内存中,数组是一块连续的区域
2.数组需要预留空间

优缺点:

优点:

1.随机访问性强,查找速度快,时间复杂度为O(1),因为数组的内存是连续的,想要访问那个元素,直接从数组的首地址向后偏移就可以访问到了。

缺点:

1.头插和头删的效率低,插入数据时,待插入位置的元素和他后面的所有元素都需要向后搬移,删除数据时,待删除位置后面的所有元素都需要向前搬移。时间复杂度为O(N)
2.空间利用率不高
3.内存空间要求高,必须有足够的连续的内存空间
4.数组空间的大小固定,不能动态拓展。扩容的话,就涉及到需要把旧数组中的所有元素向新数组中搬移。

5.数组的空间是从栈分配的。(栈:先进后出)

数组 与链表的区别:

不同:

链表是链式的存储结构;数组是顺序的存储结构
链表通过指针来连接元素与元素,数组则是把所有元素按次序依次存储。

链表的插入删除元素相对数组较为简单,不需要移动元素,且较为容易实现长度扩充,但是寻找某个元素较为困难;

相同:

两种结构均可实现数据的顺序存储,构造出来的模型呈线性结构

上一篇:react源码解析10.commit阶段


下一篇:PyQt5线程队列-----ThreadLoop