ArrayList和LinkedList的区别
1、底层数据结构的差异：
ArrayList底层是数组，是连续的内存单元
LinkedList底层是链表，是不连续的内存单元
2、数据结构引发的特征：
ArrayList 查询快，因为是连续的内存地址；增删慢，因为要发生数据迁移
LinkedList 查询慢，因为要通过链表的指针挨个寻找，增删快，因为只需要移动前后节点的指针指向即可。
3、ArrayList细节
增加 添加到末尾，数组初始容量是10，满了需要扩容，按原来容量的15倍进行扩容，源码里是按位运算，再将原来的元素复制到新数组里面。
这个是给你看的注释版:
import javautilLinkedList;
import javautilScanner;
public class Test6 {
int[][] array;
int m = 0, n = 0;
LinkedList<String> quere = new LinkedList<String>();
public Test6() {
quereadd("r");
quereadd("d");
quereadd("l");
quereadd("u");
}//定义了一个List里面装了["u","l","d","r"]四个String类型的东西
//从后面的应用来,"u"代表的是up,这个程序做的是根据给定数字X,构建
//出一个一维二维长均为X的数组,数组中以顺时针的方式用数字1到XX进行填充
//可以想象成蛇行的往里面盘绕
//这里的"u"也就是从下往上填充的意思了,其他的就不用我说了吧,"l"=left,"d"=down,"r"=right
public void printTest6(int N) {
array = new int[N][N];
for (int i = 1; i <= N N; i++) {
array[m][n] = i;
indexControl(quere, N);
}//数组赋值执行完毕
//接下来打印出数组
for (int i = 0; i < N; i++) { //N 行
for (int j = 0; j < N; j++) { //N 列
Systemoutprint(array[i][j] + "\t");//输出二维数组 "\t"是一个tab键符号
}
//每打完一组二维的数据,加换行
Systemoutprintln();//换行
Systemoutprintln();//换行
}
}
private void indexControl(LinkedList<String> quere, int N) {
String method = querepeek();
//调用peek()返回链表的头部节点,对于初始状态["u","l","d","r"]来说,返回的是"r"
if (methodequals("r")) {
//如果头部节点是"r",换句话说具体填充的时候就是从左往右先开始填充
//这时候的填充 *** 作,对于二维数组来说自然就是固定第一维不变,第二维递增了
n++;//固定第一维不变,第二维做递增 *** 作
if ((n == N - 1) || array[m][n + 1] != 0) {
//这种 *** 作的停止条件是走到了数组的边缘,也就是n == N - 1,因为n是从0开始发番
//另一种终止条件就是找到了一个已经被赋值过了的位置
quereadd(querepoll());
//条件终止之后就应该换方向了调用poll方法获得头节点,初始状态就是"r",
//然后poll方法还会把"r"从原始链表中删除,因此调用完poll之后原始链表应该变成了
//["u","l","d"],然后在调用add方法,把"r"追加到尾部,此时链表就变成["r","u","l","d"]
//下一步再取头就是"d"了,也就是开始往下走
}
} else if (methodequals("d")) {
//这里,如果头节点是"d",也就是从上往下开始赋值了,
//这时候应该是保持第二维坐标不变,第一维坐标递增
m++;//固定第二维不变,第一维做递增 *** 作
if ((m == N - 1) || array[m + 1][n] != 0) {
//这种 *** 作的停止条件是走到了数组的边缘,也就是m == N - 1,因为m是从0开始发番
//另一种终止条件就是找到了一个已经被赋值过了的位置
quereadd(querepoll());
//条件终止开始换方向,把"d"放在链表的尾部,"l"成了头
}
} else if (methodequals("l")) {
//这里,如果头节点是"l",也就是从右往左开始赋值了,
//这时候应该是保持第一维坐标不变,第二维坐标递减
n--;//固定第一维不变,第二维做递减 ***
if ((n == 0) || array[m][n - 1] != 0) {
//这种 *** 作的停止条件是走到了数组的边缘,也就是n == 0
//另一种终止条件就是找到了一个已经被赋值过了的位置
quereadd(querepoll());
//条件终止开始换方向,把"l"放在链表的尾部,"u"成了头
}
} else {
//这里,如果头节点是"u",也就是从下往上开始赋值了,
//这时候应该是保持第二维坐标不变,第一维坐标递减
m--;//固定第二维不变,第一维做递减 ***
if (array[m - 1][n] != 0) {
//终止条件就是找到了一个已经被赋值过了的位置这里不把数组边界作为判断条件是因为,
//可以保证在执行到这个部分的时候,数组的上部边界已经全部有值
quereadd(querepoll());
//条件终止开始换方向,把"u"放在链表的尾部,"r"成了头
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(Systemin);//将输入流交给scan对象
Systemoutprintln("请输入矩形的大小：");
int num = scannextInt();//scan对象获得从控制台输入的东西
new Test6()printTest6(num);//根据输入的数值构建数组
}
}
另外,程序不够严密,有障害,输入不是大于1的正整数就会挂,下面是修正版:
package Date0906Date0906_Test6;
import javautilLinkedList;
import javautilScanner;
public class Test6_Up {
int[][] array;
int m = 0, n = 0;
LinkedList<String> quere = new LinkedList<String>();
public Test6_Up() {
quereadd("r");
quereadd("d");
quereadd("l");
quereadd("u");
}
public void printTest6(int N) {
array = new int[N][N];
for (int i = 1; i <= N N; i++) {
array[m][n] = i;
indexControl(quere, N);
}
for (int i = 0; i < N; i++) { //N 行
for (int j = 0; j < N; j++) { //N 列
Systemoutprint(array[i][j] + "\t");//输出二维数组
}
Systemoutprintln();//换行
Systemoutprintln();//换行
}
}
private void indexControl(LinkedList<String> quere, int N) {
String method = querepeek();
if (methodequals("r")) {//从左往右写二维数组
n++;
if ((n == N - 1) || ( N !=1 && array[m][n + 1] != 0 )) {
//如果N为1或者检索到边界,或者检索到已经被赋值的点,重置链表,换赋值方向
quereadd(querepoll());
}
} else if (methodequals("d")) {//从上往下写二维数组
m++;
if ((m == N - 1) || ( N !=1 && array[m + 1][n] != 0 )) {
//如果N为1或者检索到边界,或者检索到已经被赋值的点,重置链表,换赋值方向
quereadd(querepoll());
}
} else if (methodequals("l")) {//从右往左写二维数组
n--;
if ((n == 0) || ( N !=1 && array[m][n - 1] != 0 )) {
//如果N为1或者检索到边界,或者检索到已经被赋值的点,重置链表,换赋值方向
quereadd(querepoll());
}
} else {//从下往上写二维数组
m--;
if (N !=1 && array[m - 1][n] != 0) {
//如果N为1或者检索到已经被赋值的点,重置链表,换赋值方向
quereadd(querepoll());
}
}
}
public static void main(String[] args) {
Scanner scan = null;
Systemoutprintln("请输入矩形的大小：");
int num = 0;
while ( true ) {
scan = new Scanner(Systemin);
//用try捕获异常,当输整数以外的内容时给提示和再次输入的机会
try {
num = scannextInt();
} catch (Exception e) {
Systemoutprintln("请输入正整数");
continue;
}
//如果发现输入的数字是非正数,则要求再次输入
if ( 0 >= num ) {
Systemoutprintln("请输入正整数");
continue;
}
break;
}
new Test6_Up()printTest6(num);
}
}
这是将数据写入链表 你的程序比较乱而且没有注释改起来比较费劲，
你第二个函数的功能是计算一个节点数据中字符串的长度还是计算链表中元素的个数？表达不明确！
SLNode LinkedListInit()
{
int N
LinkedList L;
L=(LinkedList)malloc(sizeof (SLNode));
do{
printf("Please Enter Data:");
scanf("%d",&L->data);//添加数据到链表
L->next=L;
printf("停止输入数据请按0继续请按1！");
printf("Enter:");
scanf("%d",&N);
}while(N!=0);
return L;
}
#include<stdioh>
#include<stdlibh>
typedef struct node{
int data;
struct node next;
}Linkedlist;结构体里面有一个整型的data变量和一个指向next域的next指针
定义了一个结构体
下面这个函数看函数名就是创建一个链表
Linkedlist LinkedListCreate(int a[5])
Linkedlist p,L,tail;
这是定义了linkedlist类型的三个变量
L=(struct node)malloc (sizeof(struct node));
为L申请了一个空间。空间大小sizeof（struct node），类型是struct node
tail=L;
这个是把tail指向了L
因为你这个函数的参数是一个有个数据的数组
for (int i=0;i<5;i++)
{
p=(struct node)malloc (sizeof(struct node));
这个还是申请空间。。。这是给p申请的大小和类型和上面那个一样
p->data=a[i];
然后把你传进来的数组的所存的数赋给p的data域。。。也就是把数组的数开辟一个空间存起来
tail->next=p;然后tail的的next域指向p
tail=p;把p移到p的上面那个空间里面。。这样看的话。。。你所存的数都是是逆序存储的。。因为你每次赋值都是给你所存的这个链表的上面那个节点赋值
}
tail->next=NULL;存完之后把next指向空。。。这个时候的太
return L;然后把这个链表的首地址返回就是相当于把你村的这五个数的第一个地址返回
}
这个就是打印链表了
因为你新村的那个数都是之前的那个数的上面那个节点。。。所以。。。打印的时候会是你原来的按个数组顺寻的逆序打印
void LinkedListPrint(Linkedlist L)
{
Linkedlist p;
p=L->next;
打印就是当这个链表的的next域不指向空的时候就打印这个节点的data域
while (p!=NULL)
{
printf ("%d",p->data);
p=p->next;
}
}
主函数
void main()
{
int a[5];整型数组
for (int i=0;i<=5;i++)
{循环五次。。。为数组赋值
scanf("%d",&a[i]);
}
Linkedlist L;定义一个L
L=LinkedListCreate(a);创建链表
LinkedListPrint(L);打印链表
}
这个程序的主要目的就是把输入的五个数逆序打印出来。。。用到了结构体的创建和打印。。。
#include <stdlibh>
#include <stdioh>
typedef int DataType ; //数据类型
/--链表节点描述结构体--/
struct _List_Node_
{
DataType data ; //定义数据节点
struct _List_Node_ pNext ; //定义指针变量,存放下一个节点的地址
};
typedef struct _List_Node_ LinkNode_stru ;
/---链表描述结构体---/
struct _Linked_List_
{
struct _List_Node_ pHead ; //定义头指针
struct _List_Node_ pTail ; //定义尾指针
int clen ; //定义整型变量，存放当前链表长度
};
typedef struct _Linked_List_ LinkedList_stru ;
LinkedList_stru LinkedList_Create(); //创建一个链表，并返回其首地址
LinkNode_stru List_Create_Node(DataType value); //创建一个链表节点，返回首地址
int LinkedList_Add_Tail(LinkedList_stru list,DataType value); //向链表中添加数据(尾插法，即从链表的尾部开始添加)
int LinkedList_Show(LinkedList_stru list); //显示链表，将链表中的内容打印出来
int LinkedList_Destroy(LinkedList_stru list); //销毁链表，释放空间
LinkNode_stru LinkedList_Search(LinkedList_stru list,DataType value); //在链表中搜索数据
int LinkedList_Sort_Ascend(LinkedList_stru list); //对链表中的数据按升序进行排序
/ 测试数据 /
int a[] = {2,5,8,12,15,24,36}; //集合A
int b[] = {3,8,11,16,24,30,45,56}; //集合B
int main()
{
LinkedList_stru La, Lb, Lc;
int num1, num2, num3;
int i = 0, j = 0;
LinkNode_stru p, q;
LinkNode_stru result ;
/ 1创建链表La、Lb、Lc /
La = LinkedList_Create();
Lb = LinkedList_Create();
Lc = LinkedList_Create();
/ 2将集合A和集合B的元素分别存入链表La和Lb中 /
num1 = sizeof(a)/sizeof(a[0]);
for(i=0; i<num1; i++)
{
LinkedList_Add_Tail(La,a[i]);
}
num2 = sizeof(b)/sizeof(b[0]);
for(i=0; i<num2; i++)
{
LinkedList_Add_Tail(Lb,b[i]);
}
/ 3显示链表，将链表中的内容打印出来 /
LinkedList_Show(La);
printf("\n");
LinkedList_Show(Lb);
printf("\n");
/ 4将A∪B存入链表Lc /
p = La->pHead->pNext ;
q = Lb->pHead->pNext ;
for(i=0; i<La->clen; i++)
{
if(NULL != p)
{
LinkedList_Add_Tail(Lc,p->data);
p = p->pNext ;
}
}
for(j=0; j<Lb->clen; j++)
{
if(NULL != q)
{
result = LinkedList_Search(Lc,q->data) ;
if(NULL == result)
{
LinkedList_Add_Tail(Lc,q->data);
}
q = q->pNext ;
}
}
/ 5将链表Lc进行升序排列 /
LinkedList_Sort_Ascend(Lc);
printf("将A∪B存入链表Lc,排序后的链表Lc中的数据为：\n");
LinkedList_Show(Lc); //显示链表，将链表中的内容打印出来
printf("\n");
LinkedList_Destroy(La); //销毁链表，释放空间
LinkedList_Destroy(Lb); //销毁链表，释放空间
LinkedList_Destroy(Lc); //销毁链表，释放空间
return 0;
}
/
函数名: LinkedList_Create()
时 间: 2017年2月2日 18:41:49
说 明: 创建一个链表，并返回其首地址
参 数: 无
/
LinkedList_stru LinkedList_Create()
{
LinkedList_stru list ;
list = (LinkedList_stru)malloc( sizeof(LinkedList_stru) ) ;
list->pHead = List_Create_Node(0);
list->pTail = list->pHead ;
list->clen = 0 ;
return list ;
}
/
函数名: List_Create_Node(DataType value)
时 间: 2017年2月2日 18:41:33
说 明: 创建一个链表节点，返回首地址
参 数: int value 为节点中数据的值
/
LinkNode_stru List_Create_Node(DataType value)
{
LinkNode_stru node ;
node = (LinkNode_stru )malloc(sizeof(LinkNode_stru));
node->data = value ;
node->pNext = NULL ;
return node ;
}
/
函数名: LinkedList_Add_Tail(LinkedList_stru list,DataType value)
时 间: 2017年2月2日 18:42:49
说 明: 向链表中添加数据(尾插法，即从链表的尾部开始添加)
参 数: LinkedList_stru list,DataType value
/
int LinkedList_Add_Tail(LinkedList_stru list,DataType value)
{
LinkNode_stru pNew ;
pNew = List_Create_Node(value);
/-- 断开尾指针与前面的连接，并插入数据 --/
pNew->pNext = list->pTail->pNext ;
list->pTail->pNext = pNew ;
list->pTail = pNew ;
if(NULL == list->pTail)
{
return -1 ;
}
list->clen ++ ;
return 0 ;
}
/
函数名: LinkedList_Show(LinkedList_stru List)
时 间: 2017年2月2日 18:46:47
说 明: 显示链表，将链表中的内容打印出来
参 数: LinkedList_stru List
/
int LinkedList_Show(LinkedList_stru list)
{
LinkNode_stru p ;
p = list->pHead->pNext ;
/--- 判断出错 ---/
if(0 == list->clen)
{
printf("链表内容为空，无法输出数据！！！\n") ;
}
else if(list->clen < 0)
{
return -1 ;
}
printf("该链表的长度为: %d \n",list->clen);
printf("链表的内容如下: \n");
while(NULL != p)
{
printf("%d ",p->data);
p = p->pNext ;
}
printf("\n");
return 0 ;
}
/
函数名: LinkedList_Destroy(LinkedList_stru list)
时 间: 2017年2月2日 18:46:57
说 明: 销毁链表，释放空间
参 数: LinkedList_stru list
/
int LinkedList_Destroy(LinkedList_stru list)
{
LinkNode_stru p = list->pHead->pNext ;
LinkNode_stru tmp ;
while(NULL != p)
{
tmp = p ;
p = p->pNext ;
free(tmp);
}
free(list);
return 0;
}
/
函数名: LinkedList_Sort_Ascend(LinkedList_stru list)
时 间: 2017年2月2日 18:47:44
说 明: 对链表中的数据按升序进行排序
参 数: LinkedList_stru list
/
int LinkedList_Sort_Ascend(LinkedList_stru list)
{
LinkNode_stru p = list->pHead->pNext;
LinkNode_stru tmp ;
int i=0, j=0, k=0;
for(i=1; i <= list->clen; i++)
{
tmp = p->pNext ;
for(j=i+1; j <= list->clen; j++)
{
if(p->data > tmp->data)
{
k = p->data ;
p->data = tmp->data ;
tmp->data = k ;
}
tmp = tmp->pNext ; //指针往后移一个节点
}
p = p->pNext ; //指针往后移一个节点
}
return 0;
}
/
函数名: LinkedList_Search(LinkedList_stru list,DataType value)
时 间: 2017年2月2日 19:34:11
说 明: 在链表中搜索数据
参 数: LinkedList_stru list,DataType value
/
LinkNode_stru LinkedList_Search(LinkedList_stru list,DataType value) //在链表中搜索数据
{
LinkNode_stru p = list->pHead->pNext ;
while((p != NULL) && (p->data != value))
{
p = p->pNext ;
}
return p ;
}
输出结果如下：
是双向链表。
LinkedList是一个可以存放不同类型且长度可以变的数据集合。在内存中元素不连续分配，每个元素都有记录前后节点位置信息。
LinkedList的优势在于1 LinkedList提供了4个不同位置的添加数据的方法，分别为链头插入，链尾插入，节点前插入，节点后插入。2 由于LinkedList是双向链表，在查询数据方面提供了“从前往后”和“从后往前”两个查询方法。
以上就是关于linkedlist和linklist的区别全部的内容，包括:linkedlist和linklist的区别、请把下列一段java代码加上注释： 谢谢哈、线性表 单向循环链表的 *** 作（C语言）等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）