浅谈数组和链表
时光太瘦 人气:0写在前面：
数组和链表是数据结构中最基础的两种结构,其他的都是由这两者转化而来；
因此，掌握这两种结构至关重要！下面，时光就带大家来学习一下数组和链表；
思维导图：
1，什么是线性表？
线性表是具有相同类型的n（>=0）个数据元素的有限序列（a0,a1,a2,…,an），ai是表项，n是表长度；
那么为什么要提到线性表呢？
因为数组和链表都是线性表的结构，只不过它们的存储方式不一样；
根据存储方式不同，可将线性表分为顺序表和链式表；
线性表是数据结构中的逻辑结构。可以存储在数组上，也可以存储在链表上。
一句话，用数组来存储的线性表就是顺序表。
2，数组和链表
数组：在内存中，是一块连续的内存区域；
链表：是由不连续的内存空间组成；
3，数组和链表的区别
数组优点： 随机访问性强，查找速度快（连续内存空间导致的）；
数组缺点： 插入和删除效率低 可能浪费内存 内存空间要求高，必须有足够的连续内存空间。数组大小固定，不能动态拓展链表的优点： 插入删除速度快 内存利用率高，不会浪费内存 大小没有固定，拓展很灵活。（每一个数据存储了下一个数据的地址，增删效率高）
链表的缺点：不能随机查找，必须从第一个开始遍历，查找效率低
4，数组和链表的代码实现
说了这么多，让我们用代码来写一个数组和链表。
数组：
1，先写一个实体类DynamicArray；
主要包括属性有数组容量，结点数据和数组长度；
1package com.java.model;
2
3public class DynamicArray {
4 //动态数组最大容量
5 public final static int capacity = 100;
6
7 //顺序表的结点数据
8 public int[] data;
9 //顺序表的长度，用来标识数组中的元素个数
10 public int size;
11
12 //构造函数
13 public DynamicArray(int[] data, int size) {
14 this.data = data;
15 this.size = size;
16 }
17}
2，再写数组方法类DynamicArrayDao；
主要包括数组的各种操作方法，插入、查找等；
1package com.java.dao;
2
3import com.java.model.DynamicArray;
4import static com.java.model.DynamicArray.capacity;
5
6public class DynamicArrayDao {
7
8 //初始化数组
9 public DynamicArray Init_Array(){
10 //数组数据域初始化
11 int[] data1=new int[capacity];
12
13 //DynamicArray初始化
14 DynamicArray myArray=new DynamicArray(data1,0);
15
16 //数组赋值
17 for(int i=0;i<capacity;i++){
18 myArray.data[i]=0;
19 }
20 return myArray;
21 }
22
23 //插入指定值
24 public void PushBack_Array(DynamicArray array,int value){
25 if(array==null){
26 return;
27 }
28 //如果线性表容量小于或等于数组容量
29 if(array.size==capacity){
30 return;
31 }
32 //插入元素
33 array.data[array.size]=value;
34 array.size++;
35 }
36
37 //根据位置删除
38 public void RemoveByPos_Array(DynamicArray array,int pos){
39 if (array == null){
40 return;
41 }
42 //判断位置是否有效
43 if(pos < 0 || pos >= array.size){
44 return;
45 }
46 //删除元素
47 for (int i = pos; i < array.size -1; i ++){
48 array.data[i] = array.data[i + 1];
49 }
50 array.size--;
51 }
52
53 //查找元素,返回该值第一次出现时对应的下标位置
54 public int Find_Array(DynamicArray array,int value){
55 if(array==null){
56 return -1;
57 }
58 //找到该值第一次出现的位置，-1表示没有找到；
59 int pos=-1;
60 for(int i=0;i<array.size;i++){
61 if(array.data[i]==value){
62 pos=i;
63 break;
64 }
65 }
66 return pos;
67 }
68
69 //根据位置查找到某个元素
70 public int At_Array(DynamicArray array,int pos){
71 if(array==null){
72 return -1;
73 }
74 return array.data[pos];
75 }
76
77 //根据值删除
78 public void RemoveByValue_Array(DynamicArray array,int value){
79 if(array==null){
80 return;
81 }
82 //首先找到该值对应的数组下标
83 int pos=Find_Array(array,value);
84 //调用根据位置删除的方法
85 RemoveByPos_Array(array,pos);
86 }
87
88 //打印
89 public void Print_Array(DynamicArray array){
90 if(array==null){
91 return;
92 }
93 for(int i=0;i<array.size;i++){
94 System.out.print(array.data[i]+",");
95 }
96 }
97
98 //清空数组
99 public void Clear_Array(DynamicArray array){
100 if(array==null){
101 return;
102 }
103 for(int i=0;i<array.size;i++){
104 array.data[i]=0;
105 }
106 array.size=0;
107 }
108
109 //获得动态数组当前元素个数
110 public int Size_Array(DynamicArray array){
111 if(array==null){
112 return -1;
113 }
114 return array.size;
115 }
116}
3，主函数Main；
包括测试各种函数等；
1package com.java.main;
2
3import com.java.dao.DynamicArrayDao;
4import com.java.model.DynamicArray;
5import static com.java.model.DynamicArray.capacity;
6
7public class DynamicArrayMain {
8 public static void main(String[] args) {
9 DynamicArrayDao dynamicArrayDao=new DynamicArrayDao();
10 //初始化动态数组
11 DynamicArray myArray=dynamicArrayDao.Init_Array();
12 System.out.println("初始化动态数组:");
13 //获取容量
14 System.out.println("数组容量:"+capacity);
15 System.out.println("数组实际大小:"+dynamicArrayDao.Size_Array(myArray));
16 //插入元素
17 for(int i=0;i<10;i++){
18 dynamicArrayDao.PushBack_Array(myArray,i);
19 }
20 System.out.println();
21
22 System.out.println("插入元素之后:");
23 //获取容量
24 System.out.println("数组容量:"+capacity);
25 System.out.println("数组实际大小:"+dynamicArrayDao.Size_Array(myArray));
26 System.out.println();
27
28 //打印插入元素
29 System.out.println("打印插入的元素:");
30 dynamicArrayDao.Print_Array(myArray);
31 System.out.println();
32
33 //根据元素位置删除元素
34 dynamicArrayDao.RemoveByPos_Array(myArray,2);
35 //根据元素值删除元素
36 dynamicArrayDao.RemoveByValue_Array(myArray,7);
37 System.out.println();
38
39 //打印删除后的数组
40 System.out.println("打印删除后的元素:");
41 dynamicArrayDao.Print_Array(myArray);
42 System.out.println();
43
44 //查找元素为5的位置
45 System.out.println();
46 System.out.print("元素5的位置为: ");
47 int pos=dynamicArrayDao.Find_Array(myArray,5);
48 System.out.println(pos);
49
50 //查找位置为7的元素值
51 System.out.println();
52 System.out.print("位置为7的元素为: ");
53 int value=dynamicArrayDao.At_Array(myArray,7);
54 System.out.println(value);
55
56 //获取容量
57 System.out.println();
58 System.out.println("此时的数组容量:"+capacity);
59 System.out.println("此时的数组实际大小:"+dynamicArrayDao.Size_Array(myArray));
60 System.out.println();
61 }
62}
运行效果：
链表：
1，先建立链表结点以及整个链表的实体类；
这里有两个实体类：
LinkNode是结点，包括结点的数据域和指针域；
LinkList是整个链表，包括头结点以及链表元素个数；
1package com.java.model;
2
3public class LinkNode {
4 //链表结点的数据域
5 public Object data;
6 //链表结点的指针域
7 public LinkNode next;
8
9 public LinkNode() {
10 super();
11 // TODO Auto-generated constructor stub
12 }
13
14 //构造方法
15 public LinkNode(Object data, LinkNode next) {
16 super();
17 this.data = data;
18 this.next = next;
19 }
20
21}
1package com.java.model;
2
3public class LinkList {
4 //链表的头结点
5 public LinkNode head;
6 //链表的元素个数
7 public int size;
8
9 public LinkList() {
10 super();
11 // TODO Auto-generated constructor stub
12 }
13
14 ///构造方法
15 public LinkList(LinkNode head, int size) {
16 super();
17 this.head = head;
18 this.size = size;
19 }
20
21}
2，再写链表方法类LinkListDao；
1package com.java.dao;
2
3import com.java.model.LinkList;
4import com.java.model.LinkNode;
5
6public class LinkListDao {
7 //初始化链表
8 public LinkList Init_LinkList(){
9 //设置头结点的指针域和数据域
10 LinkNode node=new LinkNode(0,null);
11 LinkList list=new LinkList(node,0);
12 return list;
13 }
14 //指定位置插入
15 public void Insert_LinkList(LinkList list, int pos, Object data){
16 //判断list是否有效
17 if(list==null){
18 return;
19 }
20 //判断data是否有效
21 if (data==null){
22 return;
23 }
24 //判断位置pos是否有效
25 if (pos<0 || pos>list.size){
26 //在链表的尾部插入
27 pos = list.size;
28 }
29
30 //第一步，创建新的结点，也就是待插入的结点
31 LinkNode newNode=new LinkNode(data,null);
32 //第二步，找到待插入结点前面一个结点pCurrent，并使其等于list的头结点
33 LinkNode pCurrent=list.head;
34 for(int i = 0 ; i < pos ; i++){
35 pCurrent=pCurrent.next;
36 }
37 //第三步，新结点入链表，进行插入操作
38 newNode.next=pCurrent.next;
39 pCurrent.next=newNode;
40 //第四步，链表的size要加1
41 list.size++;
42
43 }
44 //删除指定位置的值
45 public void RemoveByPos_LinkList(LinkList list, int pos){
46 if(list==null){
47 return;
48 }
49 if(pos<0||pos>=list.size){
50 return;
51 }
52 //第一步，找到待删除结点的前面一个结点pCurrent
53 LinkNode pCurrent=list.head;
54 for (int i = 0; i < pos; i++) {
55 pCurrent=pCurrent.next;
56 }
57 //第二步，进行删除操作
58 pCurrent.next=pCurrent.next.next;
59 //第三步，链表的size要减1
60 list.size--;
61 }
62 //获得链表的长度
63 public int Size_LinkList(LinkList list){
64 return list.size;
65 }
66 //查找指定元素的位置
67 public void Find_LinkList(LinkList list, Object data){
68 //注意这里要从头结点的下一个结点开始，因为头结点不存放数据信息
69 LinkNode pCurrent=list.head.next;
70 for (int i = 0; i < list.size; i++) {
71 if(pCurrent.data==data){
72 System.out.print(i+",");
73 }
74 pCurrent=pCurrent.next;
75 }
76 }
77 //返回第一个结点元素的值
78 public Object Front_LinkList(LinkList list){
79 return list.head.next.data;
80 }
81 //打印链表结点
82 public void Print_LinkList(LinkList list){
83 if(list==null){
84 return;
85 }
86 LinkNode pCurrent=list.head.next;
87 for (int i = 0; i < list.size; i++) {
88 System.out.print(pCurrent.data+",");
89 pCurrent=pCurrent.next;
90 }
91 }
92
93}
3，主函数Main；
测试各种方法类；
1package com.java.main;
2
3import com.java.dao.LinkListDao;
4import com.java.model.LinkList;
5
6public class LinkListMain {
7 public static void main(String[] args) {
8 LinkListDao linkListDao=new LinkListDao();
9 //创建链表
10 LinkList list=linkListDao.Init_LinkList();
11
12 //数据插入链表
13 linkListDao.Insert_LinkList(list, 0, "A");
14 linkListDao.Insert_LinkList(list, 1, "B");
15 linkListDao.Insert_LinkList(list, 2, "C");
16 linkListDao.Insert_LinkList(list, 3, "D");
17 linkListDao.Insert_LinkList(list, 4, "D");
18
19 //打印链表
20 System.out.println("插入数据之后的链表为:");
21 linkListDao.Print_LinkList(list);
22 System.out.println();
23
24 //删除指定位置的值
25 linkListDao.RemoveByPos_LinkList(list, 2);
26
27 //打印链表
28 System.out.println("删除元素C之后的链表为:");
29 linkListDao.Print_LinkList(list);
30 System.out.println();
31
32 //获得链表长度
33 System.out.println("链表长度为:");
34 System.out.println(linkListDao.Size_LinkList(list));
35
36 //查找值为3的位置
37 System.out.println("值为D的位置为:");
38 linkListDao.Find_LinkList(list, "D");
39 System.out.println();
40
41 //返回第一个结点元素的值
42 System.out.println("第一个结点元素为:");
43 System.out.println(linkListDao.Front_LinkList(list));
44 }
45}
运行结果：
文中代码格式是仿照MVC模式写的，建议大家也这样写，比较整齐我感觉。
这次就分享到这里了，后续还有一系列的数据结构的文章哦，请大家期待！
右下角点个再看吧！蟹蟹哦~
加载全部内容