链表Java LinkedList：如何将内容插入特定索引？

Question

上周我有一个计算机实验室，但没有得到全额学分，因为我使用ArrayList和一个数组来完成查找要放入内容的索引，并在其中插入TargetValue。有人能告诉我只使用LinkedList的正确方法吗

代码：

1. 它生成一个包含30个整数的随机列表
2. 它向后显示30个整数的列表
3. 它生成一个随机数，该随机数将超出“TargetValue”
4. 将LinkedList从最小值排序->；最大的
5. NEEDED：我希望看到在特定点将某些内容插入索引的正确方法

---

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 GENERATED\n" + 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 REVERSED\n" + 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

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