What is the time complexity of inserting an element into the middle of a linked list if you already have a filled array?

If you have a filled array and want to insert an element into the middle of a linked list, you first need to find the insertion position in the list. The time complexity of searching for an element in a linked list is O(n), as you need to traverse the elements up to the desired position.

Once the position is found, inserting an element into the linked list occurs in O(1), as it is enough to reassign the links.

Thus, the overall time complexity of inserting an element into the middle of a linked list when you have an array (which can help quickly find the index but not the node) is O(n), since searching for the node takes linear time.

If you have an array that stores references to the linked list nodes (for example, an array of pointers to list elements), then insertion can be performed in O(1), as you immediately get the required node.

Example:

// Suppose we have a linked list and an array of nodes
Node[] nodeArray = ...; // array of linked list nodes
int insertIndex = nodeArray.length / 2;
Node nodeBefore = nodeArray[insertIndex - 1];
Node newNode = new Node(value);
newNode.next = nodeBefore.next;
nodeBefore.next = newNode;
// Insertion is performed in O(1)

If there is no array of nodes, then you need to traverse the list to the desired position — O(n).