数据结构：线性表（上）

谈到线性的数据结构，那肯定离不开两个最底子的：数组和链表，固然有了数组和链表就会聊到栈和队列。
那么本篇我们就来先容数组和链表
一、数组

数组（Array） 是一种很常见的数据结构。它由相同范例的元素（element）构成，而且是使用一块一连的内存来存储。
我们直接可以利用元素的索引（index）可以盘算出该元素对应的存储地址。
数组的特点是：提供随机访问 而且容量有限。

1. 假如数组的长度为 n。
2. 访问：O（1）//访问特定位置的元素
3. 插入：O（n ）//最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
4. 删除：O（n）//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时

复制代码

• 随机访问本事：可以以o(1)时间复杂度，以下标访问某一元素
  
• 物理上一连，逻辑上一连，以是数组有下标
  
• 数组一旦初始化，长度不能被修改
  
• 当必要扩容时，必要创建新数组，将老数组的内容复制过来
  
• 在Java中数组是一个对象
  
• 优点：可以随机访问
  
• 缺点：必要一连的空间
  

1. int [] a = new int[10];

复制代码

相识完数组，肯定少不了arrylist,arrylist以后我会拿出单独的一篇来总结，我继续往下总结。
二、链表

链表（LinkedList） 固然是一种线性表，但是并不会按线性的次序存储数据，使用的不是一连的内存空间来存储数据。
链表的插入和删除操作的复杂度为 O(1) ，只必要知道目标位置元素的上一个元素即可。但是，在查找一个节点或者访问特定位置的节点的时间复杂度为 O(n) 。
使用链表结构可以降服数组必要预先知道数据大小的缺点，链表结构可以充分利用盘算机内存空间,实现灵活的内存动态管理。但链表不会节省空间，相比于数组会占用更多的空间，因为链表中每个节点存放的还有指向其他节点的指针。除此之外，链表不具有数组随机读取的优点。

• 可不停扩容
  
• 每个节点由值和next构成
  
• 有头插和尾插两种插入方式
  

假如链表中有n个元素。
访问：O（n）//访问特定位置的元素
插入删除：O（1）//必须要要知道插入元素的位置
 
构建单链表，完成头插和尾插的写法

1. /*
2.     构建单链表
3.     完成头插法，尾插法
4. */
7. //listnode代表一个节点
8. class ListNode{
9.     public int val;
10.     public ListNode next;
12.     //构造函数
13.     public ListNode(int a){
14.         this.val=a;
15.     }
16. }
17. public class LinkedList {
18.     public static void main(String[] args) {
19.         LinkedList a = new LinkedList();
20.         a.creatList();
21.         a.addFirst(66);
22.         a.addLast(77);
23.         a.dispaly();
24.     }
25.     //链表的头
26.     public ListNode head;
28.     public void creatList(){
29.         ListNode listNode1 = new ListNode(11);
30.         ListNode listNode2 = new ListNode(22);
31.         ListNode listNode3 = new ListNode(33);
32.         ListNode listNode4 = new ListNode(44);
33.         ListNode listNode5 = new ListNode(55);
35.         this.head = listNode1;
37.         listNode1.next = listNode2;
38.         listNode2.next = listNode3;
39.         listNode3.next = listNode4;
40.         listNode4.next = listNode5;
42.     }
44.     //头插法
45.     public void addFirst(int data){
46.         ListNode node = new ListNode(data);
47.         node.next = this.head;
48.         this.head = node;
49.     }
51.     //尾插法
52.     public void addLast(int data){
53.         ListNode node = new ListNode(data);
54.         if (this.head == null) {
55.             this.head = node;
56.         }else {
57.             ListNode cur = this.head;
58.             while (cur.next != null){
59.                 cur = cur.next;
60.             }
61.             cur.next = node;
62.         }
63.     }
64.     //打印链表
65.     public void dispaly(){
66.         ListNode cur = this.head;
67.         while (cur != null){
68.             System.out.print(cur.val+" ");
69.             cur = cur.next;
70.         }
71.         System.out.println();
72.     }
73. }

复制代码

常见链表分类：

• 单链表
  
• 双向链表
  
• 循环链表
  
• 双向循环链表
  

单链表 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不一连的。我们风俗性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向 null。

 循环链表 实在是一种特殊的单链表，和单链表差别的是循环链表的尾结点不是指向 null，而是指向链表的头结点。

 双向链表 包罗两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。

双向循环链表 末了一个节点的 next 指向 head，而 head 的 prev 指向末了一个节点，构成一个环。

 

• 如果必要支持随机访问的话，链表没办法做到。
  
• 如果必要存储的数据元素的个数不确定，而且必要经常添加和删除数据的话，使用链表比力合适。
  
• 如果必要存储的数据元素的个数确定，而且不必要经常添加和删除数据的话，使用数组比力合适。
  

链表和数组的区别

• 数组支持随机访问，而链表不支持。
  
• 数组使用的是一连内存空间对 CPU 的缓存机制友好，链表则相反。
  
• 数组的大小固定，而链表则自然支持动态扩容。如果声明的数组过小，必要另外申请一个更大的内存空间存放数组元素，然后将原数组拷贝进去，这个操作是比力耗时的！
  

固然讲了链表就会想到linkedlist，以后我也会单独开一篇总结一下。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。