Programming Data Structure Linked List - Data Structure

Linked List – Data Structure

-

Using Arrays in the program has some limitations of memory allocation. To understand Linked List, we need to understand these limitations first.

Understanding the Memory limitation


We know that Computer Memory consists of infinitesimal blocks or segments of memory, those are 1 byte each. -and each segment of memory has a specific address, starting from 0. Memory is a vital resource for the application to run on the Computer. An application, when running on the computer, keep asking for memory. Therefore, the OS employs a Memory Manager (MM) to track all of the memory that, which part of it is allocated as per program demands, and which part of it is free. So, any program needs memory should ask MM for it. Here, a program can not use memory more than allocated.

Limitation of Array and importance of linked list


Suppose, a programmer-declared an integer variable int someVar; and assigned a value 17 to it, someVar=17;. So, the program will ask to MM some space for the variable. The MM sees, the variable is an integer type, it needs 4 byte of memory, and it allocates the space, address starting from – 216 to 219. Again, the programmer-declared an integer Array, size-3, int Array[3];. Again, the program will ask to MM for allocating some memory for it. The MM will investigate the Array of 3 integer elements, each element will need 4 bytes of memory, so it allocates the necessary space, addresses starting from – 204 to 215.

Linked List - Data Structure

In case, the programmer needs to insert one more element into the array. So, the program asks MM to extend the range of current array address in the memory for the new element. which is not possible, because another variable 17 sitting right next to it, but MM can allocate a new set of addresses for the entire array. So, the programmer needs to copy the previous elements to the new address. But, the programmer must need to specify the size of the array. -This means programmer needs to declare a new set of Array, completely deleting the previous one. This time the programmer declares the array with a bigger size, int Array[7];. In this case, the problem is, some parts of the memory staying unused, and become wasted. So, to solve this problem the concept of the linked list comes in.

What is Linked list


A linked list is a Data Structure, in which the Objects are arranged in a Linear-Order. An Object consists of a value known as a key, and two-pointer attributes: next and prev. An Object may also contain some vassal or satellite data. Unlike an array, however, the linear-order is determined by the Array-indices. The order in the linked list is determined by a pointer in each Object. Linked lists provide a simple flexible representation for dynamic sets.

So, instead of asking a large contiguous block of memory, in case of a Linked list, program request to MM memory for separate Object.

Suppose, an element x in the list, x.next points to its successor element, x.prev points to its predecessor. In the above figure x.next indicates to y. If x.prev=NIL, the element has no predecessor, and x is therefore the first element, or, head of the list. If x.next = NIL; the element x has no successor, and is, therefore, the last element, tail of the list. In the above figure z is the tail of the list. The attribute L.head point to the first element. If L.head=NIL, the list is empty.

Form of Linked list


A list may have one of several forms. It may be either singly-linked or doubly-linked. It may be sorted or not, and it may be circular or not. If a list is singly-listed, we omit the prev pointer in each Object. If a list is sorted, the linear order of the list corresponds to the linear order of keys sorted in in the element of the list; the minimum element is then the head of the list, and the maximum element is the tail. If the list is unsorted, the element can appear in any order. In a circular list, the prev pointer of the head of the list points to the tail, and the next pointer of the tail points to the head. We can think of a circular list as a ring of elements.

linked list - Data Structure

Figure: Objects is the Memory. (a). A Doubly Linked list L representing the dynamic set {9, 12, 4, 7}. Each element in the list is an object with an attribute for the key and pointers to the next and previous objects. The next attribute of the tail and prev attribute of the head are NIL, indicated by a diagonal slash. The attribute L.head points to the head. 

Searching a linked list


The procedure LIST-SEARCH(L, k) finds the first element with key k in list L by a simple linear search, returning a pointer to this element. If no object with key k appears in the list, then the procedure returns NIL. For the linked list in above Figure (a), the call LIST-SEARCH(L, 7) returns a pointer to the second element, and the call LIST-SEARCH(L, 21) returns NIL, because, no key or element 21 is in the list.

LIST-SEARCH(L,k)
x=L.head
while x≠NIL and x.key≠k
x=x.next
return x

To search a list of n objects, the list search procedure takes Big – O(n) time in the worse case, since it may have to search the entire list.

Inserting into a linked list


An insertion operation of the linked list has been shown in the Above figure (B). The execution of LIST-INSERT(L,x), where x.key =17, the linked list has a new object with key 17 as a new head. The new object points to the old head with key 9.

LIST-INSERT(L,x)
x.next = L.head
if L.head ≠ NIL
L.head..prev = x
L.head = x
x.prev = NIL

Here, L.head.prev denotes the prev attribute of the object that L.head points to. The running time for LIST-INSERT on the list of n elements is O(1).

Deleting From the linked list


In the above figure (c), the result of subsequent call LIST-DELETE(l,x), where x points to the object with key 12. The procedure LIST-DELETE removes an element x from a linked list. It must be given a pointer to x, and it then splices x out of the list by updating pointers. To delete an element with a given key, we must first call LIST-SEARCH to retrieve a pointer to the element.

LIST-DELETE(L,x)
if x.prev ≠ NIL
x.prev.next = x.next
else L.head = x.next
if x.next≠NIL
x.next.prev = x.prev

LIST-DELETE runs in O(1) time, but if we wish to delete an element with a given key, Big O(n) time is required in the worst case, because we must first call LIST-SEARCH to find the element.

To understand more clearly about the linked list and its implementation in JAVA, I suggest this lecture.

//This is the end of general discussion on the Linked list from CS School/Coding. Next, we will focus more on the implementation of linked list.

Latest Articles

Property Decorator | Getters Setters and Deleters in Python

In this article, we will talk about the Property Decorator in Python. It enables the class functionality...

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap comparing to other languages. It stores data as a key-value...

Hash Table | Indexing | Hashing Algorithm | Python Implementation

This article will talk about a high-level view of the Hash Table. As a programmer, this technique...

Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a non-zero vector (matrix) that doesn't change its direction during linear...

Pivot Table | Microsoft Excel | Create Data Insight Easily

Pivot table in microsoft Excel is an useful function that gives us a way to create insight...

Macro Function in Microsoft Excel | Automate Repetitive Task

This article we will talk about the Macro. It is a function in microsoft excel which basically...

Must read

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap...

You might also likeRELATED
Recommended to you