线性表、链式存储结构
线性表是相对于逻辑结构，链式存储结构是相对于物理存储。即逻辑上是一个接一个，物理存储上是随机的。
链式存储的特点
关键字
头结点、尾结点、数据域、指针
特点
头结点：数据域为空，指针指向第一个结点
尾结点：数据与不为空，指针指向空
Java代码实现
查询
类结构：
- MyLink
- SelectLinkList
- SelectLinkListTest
MyLink是用来构造链式存储对象、SelectLinkList用来查询出指定位置的对象、SelectLinkListTest是测试
代码实现
MyLink.java
public class MyLink {
/**
* 数据域
*/
private int data;
/**
* 所指向的下一个对象的地址
*/
private MyLink nextLink;
public MyLink() {
}
public MyLink(MyLink nextLink) {
this.nextLink = nextLink;
}
public MyLink(int data, MyLink nextLink) {
this.data = data;
this.nextLink = nextLink;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public MyLink getNextLink() {
return nextLink;
}
public void setNextLink(MyLink nextLink) {
this.nextLink = nextLink;
}
}
SelectLinkList.java
public class SelectLinkList {
/**
* 用来帮助循环构建MyLink对象
*/
private MyLink[] links;
/**
* 假定传入MyLink[10]，即要创建10个MyLink对象。这10个对象中是不应该包含头节点的。
* 因为传入的数组中，所有位置都要包含数据；而MyLink的对象中头节点的构造方法是
* MyLink(MyLink nextLink)，所以在这里拿出来。
*/
private MyLink myLinkHeader = null;
/**
* 为了传入自定义MyLink[]的长度
* @param links
*/
public SelectLinkList(MyLink[] links) {
this.links = links;
}
/**
* 循环构建MyLink对象。
* @return
*/
public void createLink() {
//拿到长度，知道构造的节点是从哪里开始
int a = links.length;
//链式结构中除了尾节点，其他节点必须包含当前对象所指向下一个对象的地址，
//那么构造时就必须知道后一个节点的位置，所以必须从后往前构造。先构造最后一个结点。
links[a - 1] = new MyLink(a, null);
//循环构造MyLink对象，i=a-1相对于长度（个数）来说是倒数第二，所以其中links[i-1]就表示倒数第二位的元素
//，从后往前构造到links[0]，头节点需要自己手动构造。i相对于长度，所以links[0]对应i就是1，
//也就是说只能循环到i=1
for (int i = a - 1; i >= 1; i--) {
links[i - 1] = new MyLink(i, links[i]);
}
//构造头节点，指向数组第一个元素
myLinkHeader = new MyLink(links[0]);
}
/**
* 查出传入k位置的数据域和下一个节点的地址
* @param k
* @return
*/
public MyLink getLink(int k) throws Throwable {
if (k<1 || k>links.length) {
throw new Throwable("查询位置不合理");
}
//k是查找出k位置的元素，j是开始计数的位置；0是因为会多出一个头节点，先从头开始，头不计入查找的数组。
int j = 0;
//用一个MyLink对象来不断接收被重新赋对象。它先指向头
MyLink myLink = myLinkHeader;
//从头开始找，直到
while (j < k) {
myLink = myLink.getNextLink();
j++;
}
return myLink;
}
}
SelectLinkListTest.java
public class SelectLinkListTest {
public static void main(String[] args) {
//循环构造myLink
MyLink[] myLinks = new MyLink[10];
SelectLinkList selectLinkList = new SelectLinkList(myLinks);
selectLinkList.createLink();
//获取k位置的数据域中的数据
MyLink link;
try {
link = selectLinkList.getLink(6);
System.out.println("获取的数值域中数据为：" + link.getData());
} catch (Throwable throwable) {
throwable.printStackTrace();
}
}
}
结果
结果应该是：
image.png
如果输入的getLink()参数不满足条件：
image.png
插入
其特点是，在i位置插入，插入元素的指针指向原来i位置指针指向的元素，那么将原来i-1位置的元素的指针改为指向插入的元素。
类结构：
- InsertLinkList.java
- InsertLinkListTest.java
InsertLinkList构造线性表链式存储结构，并提供插入和查询方法；InsertLinkListTest测试。
代码实现
InsertLinkList
public class InsertLinkList {
/**
* 用来帮助循环构建MyLink对象
*/
private MyLink[] links;
/**
* 假定传入MyLink[10]，即要创建10个MyLink对象。这10个对象中是不应该包含头节点的。
* 因为传入的数组中，所有位置都要包含数据；而MyLink的对象中头节点的构造方法是
* MyLink(MyLink nextLink)，所以在这里拿出来。
*/
private MyLink myLinkHeader = null;
/**
* 为了传入自定义MyLink[]的长度
* @param links
*/
public InsertLinkList(MyLink[] links) {
this.links = links;
}
/**
* 循环构建MyLink对象。
* @return
*/
public void createLink() {
//拿到长度，知道构造的节点是从哪里开始
int a = links.length;
//链式结构中除了尾节点，其他节点必须包含当前对象所指向下一个对象的地址，
//那么构造时就必须知道后一个节点的位置，所以必须从后往前构造。先构造最后一个结点。
links[a - 1] = new MyLink(a, null);
//循环构造MyLink对象，i=a-1相对于长度（个数）来说是倒数第二，所以其中links[i-1]就表示倒数第二位的元素
//，从后往前构造到links[0]，头节点需要自己手动构造。i相对于长度，所以links[0]对应i就是1，
//也就是说只能循环到i=1
for (int i = a - 1; i >= 1; i--) {
links[i - 1] = new MyLink(i, links[i]);
}
//构造头节点，指向数组第一个元素
myLinkHeader = new MyLink(links[0]);
}
/**
* 在i位置屁股后面插入myLink对象
* @param myLink
* @param i
*/
public void insertLink(MyLink myLink,int i) {
MyLink myLinkMove = myLinkHeader.getNextLink();
if (i == 0) {
//在头位置插入myLink对象，让myLink对象指向头指针指向的对象，头结点指向myLink对象
myLink.setNextLink(myLinkMove);
myLinkHeader.setNextLink(myLink);
}else if (i>=1 && i<links.length-1){
//遍历获取到插入位置i的myLink对象
for (int k = 1; k < i ; k++) {
myLinkMove = myLinkMove.getNextLink();
}
//获取i位置的没有Link对象的下一对象
MyLink myLink2 = myLinkMove.getNextLink();
//插入的对象的指针为原来位置指向下一结点的指针
myLink.setNextLink(myLink2);
//将插入位的对象的指针设置为要插入的对象
myLinkMove.setNextLink(myLink);
}else {
//插入的位置超出或等于长度时，获取到末尾结点，让末尾结点的指针执行myLink对象
MyLink myLinkLast = links[links.length-1];
myLinkLast.setNextLink(myLink);
}
}
/**
* 查出传入k位置的数据域和下一个节点的地址
* @param k
* @return
*/
public MyLink getLink(int k) throws Throwable {
if (k<1 || k>links.length+1) {
throw new Throwable("查询位置不合理");
}
//k是查找出k位置的元素，j是开始计数的位置；0是因为会多出一个头节点，先从头开始，头不计入查找的数组。
int j = 0;
//用一个MyLink对象来不断接收被重新赋对象。它先指向头
MyLink myLink = myLinkHeader;
//从头开始找，直到
while (j < k) {
myLink = myLink.getNextLink();
j++;
}
return myLink;
}
}
InsertLinkListTest
public class InsertLinkListTest {
public static void main(String[] args) {
//循环构造myLink
MyLink[] myLinks = new MyLink[10];
InsertLinkList insertLinkList = new InsertLinkList(myLinks);
insertLinkList.createLink();
//插入
MyLink myLink = new MyLink(19,null );
insertLinkList.insertLink(myLink, 2);
try {
MyLink link = insertLinkList.getLink(3);
System.out.println(link.getData());
} catch (Throwable throwable) {
throwable.printStackTrace();
}
}
}
结果
image.png
