Explore topic-wise InterviewSolutions in .

Linked Lists, like arrays, are linear data structures. Unlike arrays, linked list elements are not stored in a single location; instead, pointers are used to connect the elements. Learn More.

Arrays can be used to store comparable forms of linear data, HOWEVER, they have the following drawbacks.

• Because the size of the arrays is fixed, we must KNOW the maximum number of elements ahead of time. In addition, regardless of consumption, the allocated memory is ALWAYS equal to the higher limit.
• Adding a new element to an array of elements is costly because space must be made for the new components, which requires current elements to be RELOCATED. Deletion in arrays is also expensive unless you employ some particular procedures.

Advantages of Linked List:

• A linked list is a dynamic data structure that can grow and shrink in size at runtime by allocating and deallocating memory. As a result, there is no need to specify the linked list's initial size.
• There is no memory wastage in the linked list since the size of the linked list increases or decreases at run time, hence there is no memory wastage and no need to pre-allocate memory.
• A linked list is frequently used to build linear data structures such as stacks and queues.
• The linked list makes it much easier to insert and delete items. After an element is inserted or deleted, there is no need to move it; only the address in the next pointer needs to be updated.

Disadvantages of Linked List:

• A linked list requires more memory than an array. Because a pointer is necessary to store the address of the next entry in a linked list, it consumes additional memory.
• Traversing a linked list takes longer than traversing an array. A linked list, unlike an array by index, does not provide direct access to an entry. To get to a mode at position n, for example, you have to go through all the nodes before it.
• Reverse traversing is not possible in a singly linked list, but it is possible in a doubly-linked list since each node carries a pointer to the previously connected nodes. Extra memory is necessary for the back pointer to execute this, resulting in memory waste.
• Because of the dynamic memory allocation in a linked list, random access is not possible.

Representation:

A pointer to the first node of a linked list is used to represent it. The head is the first node in the chain. The value of the head is NULL if the linked list is empty.
A list's nodes are made up of at least two parts:

• Data/Value
• A pointer to the next node (or a reference to it).

Structures can be used to represent a node in C. A linked list node containing integer data is shown below.

A LinkedList can be written as a class in Java or C#, and a Node can be expressed as a separate class. A reference to the Node class type can be found in the LinkedList class.

Brief History:

Allen Newell, Cliff Shaw, and Herbert A. Simon of RAND Corporation created linked lists as the basic data structure for their Information Processing Language in 1955–1956. The authors utilized IPL to create the Logic Theory Machine, the General Problem Solver, and a computer chess software, among other early ARTIFICIAL intelligence applications. Newell and Shaw's "Programming the Logic Theory Machine" contains the now-classic diagram of blocks representing list nodes with arrows pointing to subsequent list nodes.

Hans Peter Luhn, who recommended the use of linked lists in chained hash tables in an internal IBM memo in January 1953, was another early proponent of linked lists. The efficacy of linked lists and languages that employ these structures as their principal data representation was well established by the early 1960s.