链表操作
最近在复习数据结构
让人头疼的 hello 树哥
从最基础的链表结构来复习吧
interface ILink<E> {
public void add(E e);
}
class LinkImpl<E> implements ILink<E>{
private class Node { //保存节点的数据关系
private E data;
private Node next;//保存下一个引用
public Node (E data) {
this.data = data;
}
//第一次调用：LinkImpl.root.addNode() this = LinkImpl.root
//第二次调用 this = LinkImpl.root.next
public void addNode(Node newNode) { //保存新的node数据
if(this.next == null){
this.next = newNode;//当前节点的下一个节点为空 保存当前节点
}else {
this.next.addNode(newNode); // 如果不为空继续调用 知道下一次为为空了 那么保存
}
}
}
//------------------
private Node root;//根元素
public void add(E e) {//link类中定义的方法
if (e == null) {
return; //方法调用为空
}
//数据本身 不具有关联性 ，要想关联出来 包装在 node类中
Node newNode = new Node(e); //创建一个新节点
if(this.root == null ) { //没有根节点
this.root = newNode;//那么 第一个节点就是 newNode
}else {
this.root.addNode(newNode);//保存到合适的位置
}
}
}
class demo01{//链表操作
public static void main(String args[]) {
ILink<String> all = new LinkImpl<String>();
all.add("hello");
all.add("work");
}
}
在这个集合中追加方法
interface ILink<E> {
public void add(E e);
public int size();//个数总数
}
class LinkImpl<E> implements ILink<E>{
private class Node { //保存节点的数据关系
private E data;
private Node next;//保存下一个引用
private int count;
public Node (E data) {
this.data = data;
}
//第一次调用：LinkImpl.root.addNode() this = LinkImpl.root
//第二次调用 this = LinkImpl.root.next
public void addNode(Node newNode) { //保存新的node数据
if(this.next == null){
this.next = newNode;//当前节点的下一个节点为空 保存当前节点
}else {
this.next.addNode(newNode); // 如果不为空继续调用 知道下一次为为空了 那么保存
}
}
}
//------------------
private Node root;//根元素
private int count;
public void add(E e) {//link类中定义的方法
if (e == null) {
return; //方法调用为空
}
//数据本身 不具有关联性 ，要想关联出来 包装在 node类中
Node newNode = new Node(e); //创建一个新节点
if(this.root == null ) { //没有根节点
this.root = newNode;//那么 第一个节点就是 newNode
}else {
this.root.addNode(newNode);//保存到合适的位置
}
this.count ++;
}
@Override
public int size() {
// TODO Auto-generated method stub
return this.count;
}
}
class demo01{//链表操作
public static void main(String args[]) {
ILink<String> all = new LinkImpl<String>();
System.out.println(all.size());
all.add("hello");
all.add("work");
System.out.println(all.size());
}
}
增加了集合大小的方法简单的 如果下一个节点部位空了 count++
在增加判断集合为不为空
interface ILink<E> {
public void add(E e);
public int size();//个数总数
public boolean isEmpty(); // 判断这个集合为不为空
}
class LinkImpl<E> implements ILink<E>{
private class Node { //保存节点的数据关系
private E data;
private Node next;//保存下一个引用
private int count;
public Node (E data) {
this.data = data;
}
//第一次调用：LinkImpl.root.addNode() this = LinkImpl.root
//第二次调用 this = LinkImpl.root.next
public void addNode(Node newNode) { //保存新的node数据
if(this.next == null){
this.next = newNode;//当前节点的下一个节点为空 保存当前节点
}else {
this.next.addNode(newNode); // 如果不为空继续调用 知道下一次为为空了 那么保存
}
}
}
//------------------
private Node root;//根元素
private int count;
public void add(E e) {//link类中定义的方法
if (e == null) {
return; //方法调用为空
}
//数据本身 不具有关联性 ，要想关联出来 包装在 node类中
Node newNode = new Node(e); //创建一个新节点
if(this.root == null ) { //没有根节点
this.root = newNode;//那么 第一个节点就是 newNode
}else {
this.root.addNode(newNode);//保存到合适的位置
}
this.count ++;
}
@Override
public int size() {
// TODO Auto-generated method stub
return this.count;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return this.count == 0;
//或者 return this.root == null;
}
}
class demo01{//链表操作
public static void main(String args[]) {
ILink<String> all = new LinkImpl<String>();
System.out.println(all.size());
System.out.println(all.isEmpty());
all.add("hello");
all.add("work");
System.out.println(all.size());
System.out.println(all.isEmpty());
}
}
在增加方法 对链表中数据进行输出
interface ILink<E> {
public void add(E e);
public int size();//个数总数
public boolean isEmpty(); // 判断这个集合为不为空
public Object [] toArray(); //将集合通过数组的方式返回
}
class LinkImpl<E> implements ILink<E>{
private class Node { //保存节点的数据关系
private E data;
private Node next;//保存下一个引用
public Node (E data) {
this.data = data;
}
//第一次调用：LinkImpl.root.addNode() this = LinkImpl.root
//第二次调用 this = LinkImpl.root.next
public void addNode(Node newNode) { //保存新的node数据
if(this.next == null){
this.next = newNode;//当前节点的下一个节点为空 保存当前节点
}else {
this.next.addNode(newNode); // 如果不为空继续调用 知道下一次为为空了 那么保存
}
}
//根据递归获取数据
//第一次调用 this = LinkImpl.root
public void toArrayNode(){
LinkImpl.this.returnData [LinkImpl.this.foot ++] = this.data;
if(this.next != null){//还有下一个数据的话
this.next.toArrayNode();
}
}
}
//------------------
private Node root;//根元素
private int count;
private int foot; // 追加个脚标
private Object [] returnData;//返回的数据保存
public void add(E e) {//link类中定义的方法
if (e == null) {
return; //方法调用为空
}
//数据本身 不具有关联性 ，要想关联出来 包装在 node类中
Node newNode = new Node(e); //创建一个新节点
if(this.root == null ) { //没有根节点
this.root = newNode;//那么 第一个节点就是 newNode
}else {
this.root.addNode(newNode);//保存到合适的位置
}
this.count ++;
}
//----------------------实现
@Override
public int size() {
// TODO Auto-generated method stub
return this.count;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return this.count == 0;
//或者 return this.root == null;
}
@Override
public Object[] toArray() {
// TODO Auto-generated method stub
if(this.isEmpty()) {
return null;
}
this.foot = 0;//脚标清零
this.returnData = new Object[this.count];//根据已有的长度开辟数组
//根据node类 递归获取数据
this.root.toArrayNode();//利用Node类递归数据获取
return this.returnData;
}
}
class demo01{//链表操作
public static void main(String args[]) {
ILink<String> all = new LinkImpl<String>();
System.out.println(all.size());
System.out.println(all.isEmpty());
all.add("hello");
all.add("work");
System.out.println(all.size());
System.out.println(all.isEmpty());
Object res[] = all.toArray();
for(Object obj : res){
System.out.println(obj);
}
}
}
根据索引 获取数据
interface ILink<E> {
public void add(E e);
public int size();//个数总数
public boolean isEmpty(); // 判断这个集合为不为空
public Object [] toArray(); //将集合通过数组的方式返回
public E get(int index);//利用索引 取得数据 通过foot
}
class LinkImpl<E> implements ILink<E>{
private class Node { //保存节点的数据关系
private E data;
private Node next;//保存下一个引用
public Node (E data) {
this.data = data;
}
//第一次调用：LinkImpl.root.addNode() this = LinkImpl.root
//第二次调用 this = LinkImpl.root.next
public void addNode(Node newNode) { //保存新的node数据
if(this.next == null){
this.next = newNode;//当前节点的下一个节点为空 保存当前节点
}else {
this.next.addNode(newNode); // 如果不为空继续调用 知道下一次为为空了 那么保存
}
}
//根据递归获取数据
//第一次调用 this = LinkImpl.root
public void toArrayNode(){
LinkImpl.this.returnData [LinkImpl.this.foot ++] = this.data;
if(this.next != null){//还有下一个数据的话
this.next.toArrayNode();
}
}
@SuppressWarnings("unused")
public E getNode(int index) {
if(LinkImpl.this.foot ++ == index) {
return this.data;
}else {
return this.next.getNode(index);
}
}
}
//------------------
private Node root;//根元素
private int count;
private int foot; // 追加个脚标
private Object [] returnData;//返回的数据保存
public void add(E e) {//link类中定义的方法
if (e == null) {
return; //方法调用为空
}
//数据本身 不具有关联性 ，要想关联出来 包装在 node类中
Node newNode = new Node(e); //创建一个新节点
if(this.root == null ) { //没有根节点
this.root = newNode;//那么 第一个节点就是 newNode
}else {
this.root.addNode(newNode);//保存到合适的位置
}
this.count ++;
}
//----------------------实现
@Override
public int size() {
// TODO Auto-generated method stub
return this.count;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return this.count == 0;
//或者 return this.root == null;
}
@Override
public Object[] toArray() {
// TODO Auto-generated method stub
if(this.isEmpty()) {
return null;
}
this.foot = 0;//脚标清零
this.returnData = new Object[this.count];//根据已有的长度开辟数组
//根据node类 递归获取数据
this.root.toArrayNode();//利用Node类递归数据获取
return this.returnData;
}
//---------------------
@Override
public E get(int index) {
// TODO Auto-generated method stub
if (index > this.count){
return null;
}//索引的获取 应由node类完成
this.foot = 0;//应该通过foot控制脚标
return this.root.getNode(index);
}
}
class demo01{//链表操作
public static void main(String args[]) {
ILink<String> all = new LinkImpl<String>();
System.out.println(all.size());
System.out.println(all.isEmpty());
all.add("hello");
all.add("work");
System.out.println(all.size());
System.out.println(all.isEmpty());
Object res[] = all.toArray();
for(Object obj : res){
System.out.println(obj);
}
System.out.println(all.get(1));
}
}
增加新方法 根据索引去set
interface ILink<E> {
public void add(E e);
public int size();//个数总数
public boolean isEmpty(); // 判断这个集合为不为空
public Object [] toArray(); //将集合通过数组的方式返回
public E get(int index);//利用索引 取得数据 通过foot
public void set(int index,E data);
}
class LinkImpl<E> implements ILink<E>{
//内部node类
private class Node { //保存节点的数据关系
private E data;
private Node next;//保存下一个引用
public Node (E data) {
this.data = data;
}
//第一次调用：LinkImpl.root.addNode() this = LinkImpl.root
//第二次调用 this = LinkImpl.root.next
public void addNode(Node newNode) { //保存新的node数据
if(this.next == null){
this.next = newNode;//当前节点的下一个节点为空 保存当前节点
}else {
this.next.addNode(newNode); // 如果不为空继续调用 知道下一次为为空了 那么保存
}
}
//根据递归获取数据
//第一次调用 this = LinkImpl.root
public void toArrayNode(){
LinkImpl.this.returnData [LinkImpl.this.foot ++] = this.data;
if(this.next != null){//还有下一个数据的话
this.next.toArrayNode();
}
}
public E getNode(int index) {
if(LinkImpl.this.foot ++ == index) {
return this.data;
}else {
return this.next.getNode(index);
}
}
public E setNode(int index,E data) {
if(LinkImpl.this.foot ++ == index) {
this.data = data;
}else {
this.next.setNode(index,data);
}
return data;
}
}
//------------------
private Node root;//根元素
private int count;
private int foot; // 追加个脚标
private Object [] returnData;//返回的数据保存
public void add(E e) {//link类中定义的方法
if (e == null) {
return; //方法调用为空
}
//数据本身 不具有关联性 ，要想关联出来 包装在 node类中
Node newNode = new Node(e); //创建一个新节点
if(this.root == null ) { //没有根节点
this.root = newNode;//那么 第一个节点就是 newNode
}else {
this.root.addNode(newNode);//保存到合适的位置
}
this.count ++;
}
//----------------------实现方法
@Override
public int size() {
// TODO Auto-generated method stub
return this.count;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return this.count == 0;
//或者 return this.root == null;
}
@Override
public Object[] toArray() {
// TODO Auto-generated method stub
if(this.isEmpty()) {
return null;
}
this.foot = 0;//脚标清零
this.returnData = new Object[this.count];//根据已有的长度开辟数组
//根据node类 递归获取数据
this.root.toArrayNode();//利用Node类递归数据获取
return this.returnData;
}
//---------------------
@Override
public E get(int index) {
// TODO Auto-generated method stub
if (index > this.count){
return null;
}//索引的获取 应由node类完成
this.foot = 0;//应该通过foot控制脚标
return this.root.getNode(index);
}
@Override
public void set(int index, E data) {
// TODO Auto-generated method stub
if (index > this.count){
return ;//方法结束
}//索引的获取 应由node类完成
this.foot = 0;//应该通过foot控制脚标
this.root.setNode(index,data);//修改数据
}
}
class demo01{//链表操作
public static void main(String args[]) {
ILink<String> all = new LinkImpl<String>();
System.out.println(all.size());
System.out.println(all.isEmpty());
all.add("hello");
all.add("work");
all.set(1,"java");
System.out.println(all.size());
System.out.println(all.isEmpty());
Object res[] = all.toArray();
for(Object obj : res){
System.out.println(obj);
}
System.out.println(all.get(1));
}
}
这种时间复杂度为 N
遍历 递归