【数据结构java描述（一）】单链表类的create()方法的重写以及Node类的理解

首先我们需要知道线性表的链式结构的设计思路：

先构造结点类，然后基于结点，设计链式结构类。

Java源码中结点类Node.Java：

package com.study.test;

 

publicclass Node {

  Object data;

  Node next;

 

  Node() {

     this(null,null);

  }

 

  Node(Object data) {

     this(data,null);

  }

 

  Node(Object data, Node next) {

     this.data = data;

     this.next = next;

  }

 

  public Object getData() {

     returndata;

  }

 

  publicvoid setData(Object data) {

     this.data = data;

  }

 

  public Node getNext() {

     returnnext;

  }

 

  publicvoid setNext(Node next) {

     this.next = next;

  }

 

}

很简单，但难度在于指针变量是结点类的对象，这与我们所学的理念有所不同。尤其是在将结点的运用在单链表类的描述时，不清楚next何时是指针，何时是下一个借点。

事实上，虽然java在内存层次存在指针， java根据在栈内存里的固定内存指向堆内存的随机内存，但语法上不存在指针的概念。因此java在栈内存中

声明next，来标记所在的堆空间。

声明Node类的对象，不代表创建了Node的实例（在堆内存中占有空间），更多的是创建了一个标记，用来标记堆中某块内存。

然后我发现单链表类的create方法实现由于复用了insert()，而复杂度达到O(n^2)，因此自己设计了一个复杂度只是O(n)的实现算法，在这里分享，估计存在错误，希望大家指出。

import java.util.Scanner;

 

publicclass MyLinkList {

  publicvoid create(intn) {

     Scanner sc = new Scanner(System.in);

     MyNode curHead;

     MyNode lastHead = new MyNode(sc.next());

     for (inti = 0; i < n; i++) {

       MyNode newNode = new MyNode(sc.next());

       curHead = newNode;

       lastHead.setNext(curHead);

       lastHead = newNode;

     }

  }

}

【数据结构java描述（一）】单链表类的create()方法的重写以及Node类的理解

原文：http://blog.csdn.net/qq_22939165/article/details/44659163