Linked List vs Array | Java Fresher Interview

A linked list is a chain of nodes, where each node holds a value and a reference to the next node, and the list itself only knows about its head. The nodes can be scattered anywhere in memory; they're connected purely by those references. An array, by contrast, stores all its elements in one contiguous block of memory, so element i is located by simple address arithmetic. That difference drives the whole tradeoff. Arrays give O of one random access: I can jump straight to any index. But inserting or deleting in the middle is O of n, because everything after the spot has to shift over. Linked lists are the opposite. They have no random access at all, so reaching position k means walking k pointers from the head, which is O of k. But once I'm holding a particular node, inserting or deleting is O of one, because I just relink a couple of pointers and nothing shifts. The important caveat I always add is that the O of one insertion assumes I already have a reference to the node; if I have to find it first, that search is still O of n. I'd also mention cache locality. Because arrays are contiguous, the CPU prefetches nearby elements, so array traversal is often noticeably faster in practice than chasing scattered pointers. And each linked-list node costs extra memory for its pointer. So in real Java code I default to ArrayList, and I reach for a linked structure mainly for queue or deque patterns with lots of end insertions. For example, to insert 15 after a held node 10 in 10 -> 20 -> 30, point 15 to 20 and 10 to 15. Only two links change; an array insertion at the same position must shift 20 and 30.