Java LinkedList:如何将内容插入到特定索引

Question

我上周有一个计算机实验室，没有得到全部的学分，因为我使用数组列表和数组来完成查找哪个索引放东西，并插入TargetValue在那里。有人能告诉我正确的方法来做到这一点与LinkedLists ?

代码:

1. 生成30个整数的随机列表。
2. 反向显示30个整数列表。
3. 它会生成一个随机数，这个随机数将会输出"TargetValue"。
4. 将LinkedList从最小到最大排序。
5. 需要:我想看到正确的方式插入到它的索引在一个特定的点。

---

public class LAB11 {
    public static LinkedList<Integer> LabList = new LinkedList<Integer>();
    public static ArrayList<Integer> LabArray = new ArrayList<Integer>();
    public static LinkedList<Integer> SortedList = new LinkedList<Integer>();
    public static int TargetValue;
    public static void main(String args[]){
        PopulateList();
        BackwardsList();
        GenerateTarget();
        SortList();
    }
    public static void PopulateList(){
        Random random = new Random();
        int range = 100 - 1 + 1;
        for(int i = 0 ; i < 30 ; i++){
            int rn = random.nextInt(range) + 1;
            LabList.add(rn);
            LabArray.add(rn);
        }
        System.out.println("LINKED LIST GENERATEDn" + LabList);
    }
    public static void BackwardsList(){
        LabList.clear();
        for(int i = 29 ; i >= 0 ; i--){
            int temp = LabArray.get(i);
            LabList.add(temp);
        }
        System.out.println("nLINKED LIST REVERSEDn" + LabList);
    }
    public static void GenerateTarget(){
        Random random = new Random();
        int range = 100 - 1 + 1;
        TargetValue = random.nextInt(range) + 1;
        System.out.println("nTARGET VALUE: " + TargetValue);
    }
    public static void SortList(){
        Collections.sort(LabList);
        System.out.println(LabList);
        // NEEDED: INSERT TAGETVALUE INTO THE INDEX THAT KEEPS NUMBERS IN ORDER STILL.
    }
}

Answer 1

传统的LinkedList数据结构不支持在指定索引上插入O(1)。LinkedList的定义结构是每个元素持有一个指向下一个元素的指针。

让我们看一个简单的实现:

public class Node {
  int x;
  Node next;
  public Node(int x)
  {
     this.x = x;
  }
}

我们可以这样创建一个LinkedList:

Node n1 = new Node(3);
n1.next = new Node(4);
n1.next.next = new Node(1);
n1.next.next.next = new Node(0);
3 --> 4 --> 1 --> 0

注意，在n1中唯一可以立即获得的对象。为了到达其他地方，我们需要穿越LinkedList。同样的逻辑也适用于对指定索引的插入。必须遍历结构体，才能到达可以执行插入操作的点。

下面的伪代码展示了如何实现

Node current = n1
Node insertionNode = new Node(10);
int insertionInx = 2
int currentIdx = 0
while currentIdx < insertionIdx - 1
  current = current.next
  currentIdx++
temp = current.next
current.next = insertionNode
current.next.next = temp

当然，您将不得不处理边缘情况，如插入索引超过列表的长度，但这应该有助于您更好地理解数据结构。