课时138:根据索引取得数据
摘要:
1. 索引访问的需求
2. 索引访问的方法
01. 索引访问
链表也可以像数组一样进行索引数据的获取。在这种情况下,我们可以继续使用递归的形式来完成。
注:数据都有索引,索引(Index)是用于标识数据位置的整数值。在链表中,索引从 0 开始,依次递增。例如,第一个数据的索引为 0,第二个数据的索引为 1,以此类推。通过索引,我们可以快速定位并获取特定位置的数据。为了根据索引获取数据,我们需要遍历链表,逐个判断当前节点的索引是否与目标索引匹配。
如果匹配,则返回该节点的数据;如果不匹配,则继续遍历下一个节点,直到找到目标索引或遍历结束。用 Foot 获取索引值,实现针对索引的控制。索引值不可超过数据量。
注:通过索引访问链表中的数据,可以方便地获取指定位置的数据项,类似于数组的访问方式。
02. 索引访问的方法
1.在 ILink 接口中添加 get(int index)
方法
interface ILink<E> {//设置范型避免安全隐患 public void add(E e);//增加数据的个数 public int size();//获取数据的个数 public Object [] toArray(); public boolean isEmpty(); public E get(int index); // 根据索引获取数据 }
2.在 Node 类中添加 getNode(int index)
方法
public E getNode(int index) { if (LinkImpl.this.foot ++== index) {//索引相同 return this.data; //返回当前数据 } else { return this.next.getNode(index); } }
3.在 LinkImpl 子类中实现 get(int index)
方法
public E get(int index) { if (index >= this.count) {// 索引应该在指定的范围内 return null; }//索引数据的获取应该由 node 位完成 this.foot = 0;//重制索引的下标 return this.root.getNode(index); }
4.进行测试
public class LinkDemo { public static void main(String[] args) { ILink<String> all = new LinkImpl<String>(); System.out.println("【增加之前】数据个数:" + all.size()+"、是否为空集合:"+all.isEmpty()); all.add("Hello"); all.add("World"); all.add("MLDN"); System.out.println("【增加之后】数据个数:" + all.size()+"、是否为空集合:"+all.isEmpty()); System.out.println("------数据获取的分割线-------"); System.out.println(all.get(0)); System.out.println(all.get(1)); System.out.println(all.get(4)); // 索引超出范围 } }
执行后结果为:
通过以上步骤,我们实现了通过索引访问链表数据的能力。 这种方法与数组的访问方式类似,但需要注意的是,数组获取数据的时间复杂度为 O(1),而链表获取数据的时间复杂度为 O(n),其中 n 是链表的长度。
这是因为链表需要从头开始遍历,直到找到目标索引对应的数据。 因此,在需要频繁进行索引访问的场景下,数组可能更适合。