黑马程序员技术交流社区

标题: 单链表实现 [打印本页]

作者: EscapedPupil 时间: 2019-6-6 12:41
标题: 单链表实现
近日，在学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;
        }
}
---------------------

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2