普通单链表的创建有些复杂，于是可以通过数组实现简单链表的一些功能。

优秀博客链接：https://blog.csdn.net/Nanrdml/article/details/104136221

数组构建链表

单链表的特点即表中存放一个数据的同时，也通过指针指向下一个数据域，于是需要

• 建立两个数组data[] 存放数据，r[] 存放下一个数据的下标，为了方便0号下标的位置就不存放元素了；
• n标记一下链表实际最大长度；
• front标记表头结点，开始front = 1；

***注意链表中最后一个结点的next指针为空，所以将r[]中最后一个数据的下标记为-1
——————————————————New_List类的一部分————————————————

int front;
private int n = 1;
int[] data = new int[100];
int[] r = new int[100];

public New_List(int n){
	this.n = n;
	front = 1;
}

————————————————————————开始生成一个链表————————————————————————

int n = sc.nextInt();
New_List L1 = new New_List(n);
init(L1, n);	//上面三句写在Main()方法中
public static void init(New_List L, int n){
	for(int i = 1; i <= n; ++i){
		L.data[i] = sc.nextInt();
		if(i != n)
			L.r[i] = i + 1;
		else
			L.r[i] = -1;
	}
}

————————————————————输出这个链表————————————————————

public void print(){
	int cnt = front;
	while(cnt != -1){
		System.out.print(data[cnt] +" ");
		cnt = r[cnt];//找下一个结点
	}
	System.out.println();
}

链表的插入

回顾单链表的插入操作q->next = pre->next; pre->next = q;
于是有了在第count个元素前添加值temp
算法实现

• 按照输出链表的思路，开始令pre=front，然后pre=r[pre]；
• 我们要找第count个元素，循环count-1次即可；
• count-1次即可？这样指向的要添加的位置，我们应该找到count前一个位置；
• 没错就是count-2次；
• 另外需要空出来一个位置存放新的结点。
  ————————————————————实现起来比链表还复杂些———————————————————

  public void Add(int count, int temp){
  	++n;//新加了结点，链表最大长度+1
  	if(count > n)
  		return;
  	int cnt = 1;
  	while(cnt <= n){//寻找一个空着的位置cnt
  		if(data[cnt] == 0)
  			break;
  		++cnt;
  	}
  	data[cnt] = temp;
  	if(count == 1){//特别地，当插在头结点前面，front要指向cnt
  		r[cnt] = front;
  		front = cnt;
  		return;
  	}
  	int pre = front;
  	while(count > 2){
  		pre = r[pre];
  		--count;
  	}
  	if(count != n){
  		r[cnt] = r[pre];//q->next = pre->next;
  		r[pre] = cnt;//pre->next = q;
  	}else{//	特别地，末尾插入结点，q->next = null;
  		r[pre] = cnt;
  		r[cnt] = -1;
  	}
  }

链表的删除

要求删除第count个元素
算法实现

• 为节省空间，删除的元素的data[]和 r[]值均置为0，这是为再次插入新结点腾出位置；
• 回忆链表的删除操作pre->next = q->next，至少要找到第count的位置；
• 于是需要循环count-1次。
  ———————————————————删除较添加还是容易些————————————————————

  public void Delete(int count){
  	if(count > n)
  		return;
  	--n;
  	int cnt = front, pre = front;
  	if(count == 1){//特别地，删除第一个结点，要将front还原，以及更改front
  		cnt = r[front];
  		data[pre] = 0;
  		r[pre] = -1;
  		front = cnt;
  		return;
  	}
  	while(count > 1){
  		pre = cnt;
  		cnt = r[cnt];
  		--count;
  	}
  	r[pre] = r[cnt];//pre->next = q->next
  	data[cnt] = 0;//删除的结点进行还原
  	r[cnt] = -1;
  }

以上小小测试一下

int n = sc.nextInt();
New_List L = new New_List(n);
init(L, n);
L.print();
L.Add(1, 10);
L.print();
L.Delete(1);
L.Delete(2);
L.print();

数组实现两个有序链表合并

有了之前New_List类，两个有序链表合并就只用一个Merge()方法就行了

//生成两个链表
int n = sc.nextInt();
New_List L1 = new New_List(n);
init(L1, n);
L1.print();

n = sc.nextInt();
New_List L2 = new New_List(n);
init(L2, n);
L2.print();
//合并
Merge(L1, L2);

算法实现

• 其实和归并排序中的merge()操作大同小异了，不同点就在于遍历两数组不是顺序的，而是利用了r[]下标；

• 实现的同时就当是对归并排序的加深理解了。

  public static void Merge(New_List L1, New_List L2){
  	int cnt1 = L1.front;
  	int cnt2 = L2.front;
  	//新链表的长度初始化为0
  	New_List L3 = new New_List(0);
  	int k = 0;//记录新链表长度
  	//归并中的while(i<=a.length && j<=b.length)
  	while(cnt1!=-1 && cnt2!=-1){
  		if(L1.data[cnt1] <= L2.data[cnt2]){
  			L3.Add(++k, L1.data[cnt1]);
  			cnt1 = L1.r[cnt1];
  		}else{
  		L3.Add(++k, L2.data[cnt2]);
  			cnt2 = L2.r[cnt2];
  		}
  	}
  	while(cnt1 != -1){
  		L3.Add(++k, L1.data[cnt1]);
  		cnt1 = L1.r[cnt1];
  	}
  	while(cnt2 != -1){
  		L3.Add(++k, L2.data[cnt2]);
  		cnt2 = L2.r[cnt2];
  	}
  	L3.print();
  }

• 照着这个思路可以继续思考更多操作，其实写下了觉得，用数组实现和原始的链表相比并没有简单太多，（反而因为数组的连续这一性质，要考虑将删除的结点还原为空）不像用数组表示一些树相关的操作那么便利；

• 仅当作思维的扩展吧；最后附上完整的New_List类

  class New_List{
  	int front;
  	private int n = 1;
  	int[] data = new int[100];
  	int[] r = new int[100];
  
  	public New_List(int n){
  		this.n = n;
  		front = 1;
  	}
  	public void Add(int count, int temp){
  		++n;
  		if(count > n)
  			return;
  		int cnt = 1;
  		while(cnt <= n){
  			if(data[cnt] == 0)
  				break;
  			++cnt;
  		}
  		data[cnt] = temp;
  		if(count == 1){
  			r[cnt] = front;
  			front = cnt;
  			return;
  		}
  		int pre = front;
  		while(count > 2){
  			pre = r[pre];
  			--count;
  		}
  		if(count != n){
  			r[cnt] = r[pre];
  			r[pre] = cnt;
  		}else{
  			r[pre] = cnt;
  			r[cnt] = -1;
  		}
  	}
  	public void Delete(int count){
  		if(count > n)
  			return;
  		--n;
  		int cnt = front, pre = front;
  		if(count == 1){
  			cnt = r[front];
  			data[pre] = 0;
  			r[pre] = -1;
  			front = cnt;
  			return;
  		}
  		while(count > 1){
  			pre = cnt;
  			cnt = r[cnt];
  			--count;
  		}
  		r[pre] = r[cnt];
  		data[cnt] = 0;
  		r[cnt] = -1;
  	}
  	public void print(){
  		int cnt = front;
  		while(cnt != -1){
  			System.out.print(data[cnt] +" ");
  			cnt = r[cnt];
  		}
  		System.out.println();
  	}
  }