近日，在学Java的途中，琢磨着单链表的实现应该是由节点元素和链体构成。
那么就应该可以按照链体封装节点为内部类的方法来实现单链表。
public class LinkList(){
//链体
private class Link(){
//节点
}
}
节点类属性：需要有一个头结点（first），需要有节点存储的数据（data），
需要有当前节点指向下一节点的标识（next）。
链表的思路：first值为第一个节点地址Link first = new Link（data）；
第二个节点：first.next = new Link（data）；
第三个节点：first.next.next = new Link(data)...以此类推。
每个单链表只会有一个表头，则LinkList中成员属性仅需要添加Link first。
public class LinkList{
private Link first;
public LinkList(){
this.first = null ;//first作为成员本身值也是null，这里只是注明：
//链表创建，生成空节点对象。
}
private class Link{
public Link first;//first在此处虽然没有使用static修饰，但在链表中效果类似
public Link next;
public int data;
public Link(int data){
this.data = data;
}
}
单链表原始设计，差不多就这样。
但我们想要用其增删改元素，还需定义方法。
以下是重点，也是个人觉得的链表易错点。
public boolean isEmpty() {
return this.first == null; //判断链表是否为空。
}
private void addFirst(int data) {
this.first = new Link(data); //私有化添加第一个元素，可以并入*******处
}
public boolean add(int data) {
if (this.isEmpty()) {
this.addFirst(data); //********
}
else {
Link temp = this.first;
while (temp.next != null) { //链表着重注意点：1(个人理解):
temp = temp.next;
}
temp.next = new Link(data); ////链表着重注意点:2（个人理解）
}
return true;
}
注意点1：判断temp指向的节点的next是否指向空，
为空代表temp指向的节点的下一个节点不存在，可以添加。
注意2：这里与注意点1对比，不能用temp！=null来充当while循环的判断条件。
虽然temp是充当临时变量，指向每一个节点，
但如果temp指向了空， 那么temp = new Link(data)，
仅仅是给temp赋值。并没有添加到链体里。
可以自行测试
while (temp != null) { //链表着重注意点：1(个人理解):
temp = temp.next;
}
temp = new Link(data); ////链表着重注意点:2（个人理解）
其他方法比较好理解，就不一一赘述。如果要实现索引功能，
需要额外在Link节点添加成员index。
以下是实现了几个小功能的单链表代码：
public class LinkList<T> {
//私有化Link节点的头结点
//每个LinkList创建之初，都会自动生成一个null值的头结点
private Link first;
public LinkList() {
this.first = null;
}
private void addFirst(T data) {
this.first = new Link(data);
ensureIndex();
}
//判断是否为空
public boolean isEmpty() {
return this.first == null;
}
//添加。
public boolean add(T data) {
if (this.isEmpty()) {
this.addFirst(data);
} else {
Link temp = this.first;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new Link(data);
ensureIndex();
}
return true;
}
//遍历
public void show() {
Link temp = this.first;
System.out.print("[");
while (temp != null) {
if (temp.next != null) {
System.out.print(temp.data + ",");
} else {
System.out.print(temp.data);
}
temp = temp.next;//this.first.next = current = new Link(23) != null
}
System.out.println("]");
}
//select from index
public T getByIndex(int index) {
Link temp = this.first;
for (int i = 0; i < index; i++) {
temp = temp.next;
if (temp == null) {
throw new IndexOutOfBoundsException("不正确的索引");
}
}
return (T) temp.data;
}
//修改元素：通过比较存储值是否equals，
public boolean replace(T data, T dataNew) {
Link temp = this.first;
while (true) {
if (temp == null) {
return false;
}
if (!(temp.data.equals(data))) {
temp = temp.next;
} else {
temp.data = dataNew;
return true;
}
}
}
//删除某个元素
public boolean remove(T data) {
if (this.first == null) {
return false;
}
Link temp = this.first;
if (temp.data.equals(data)) {
this.first = temp.next;
return true;
}
while (true) {
if (temp.next == null) {
return false;
}
if (!temp.next.data.equals(data)) {
temp = temp.next;
} else {
temp.next = temp.next.next;
ensureIndex();
}
}
}
//确定元素对应索引值。
private void ensureIndex() {
Link temp = this.first;
if (temp.index != 0) {
temp.index = 0;
}
while (temp.next != null) {
if (temp.next.index != temp.index + 1) {
temp.next.index = temp.index + 1;
temp = temp.next;
} else {
temp = temp.next;
}
}
}
private class Link<T> {
public T data;
public Link next;
public Link first;
public Link(T data) {
this.data = data;
}
public int index;
}
}
--------------------- |
|
收藏
淘帖
踩
