What is the difference between linked lists and arrays

Array supports Random Access , which means elements can be accessed directly using their index, like arr[0] for 1st element, arr[6] for 7th element etc. Hence, accessing elements in an array is fast with a constant time complexity of O 1. In an array, elements are stored in contiguous memory location or consecutive manner in the memory. In case of linked list, a new element is stored at the first free and available memory location, with only a single overhead step of storing the address of memory location in the previous node of linked list.

Below we have a pictorial representation showing how consecutive memory locations are allocated for array, while in case of linked list random memory locations are assigned to nodes, but each node is connected to its next node using pointer. In case of array, memory is allocated in contiguous manner, hence array elements get stored in consecutive memory locations.

So when you have to access any array element, all we have to do is use the array index, for example arr[4] will directly access the 5th memory location, returning the data stored there. But in case of linked list, data elements are allocated memory at runtime, hence the memory location can be anywhere.

Therefore to be able to access every node of the linked list, address of every node is stored in the previous node, hence forming a link between every node. We need this additional pointer because without it, the data stored at random memory locations will be lost. We need to store somewhere all the memory locations where elements are getting stored.

Yes, this requires an additional memory space with each node, which means an additional space of O n for every n node linked list. Learn Core Java. Java Examples Java 8 Java 11 Java HTML 5 Interactive. CSS Interactive.

Learn in-demand tech skills in half the time. Early Access Courses. Assessments New. Free Trial New. For Business. For Educators. Become an Affiliate. Terms of Service. Business Terms of Service.

Careers Hiring. For Bootcamps. Blog for Business. Quality Commitment. Save Article. Improve Article. Like Article. Data storage scheme of an array. Data storage scheme of a linked list. Attention reader! Previous Applications of Heap Data Structure. Next Static Blocks in Java. Recommended Articles.