Before we start we need to know pointer and array first.
Pointer
In computer science, a pointer is a programming language object, whose value refers to (or “points to”) another value stored elsewhere in the computer memory using its memory address.
& is the address operator
* is the dereferencing operator
Pointers are frequently used in C, as they have a number of useful applications. Such as:
–Used to pass information back and forth between a function and its reference point.
–Enable the programmers to return multiple data items from a function via function arguments or to pass arrays and strings as function arguments
–Provide an alternate way to access the individual elements of an array
–Used to create complex data structures, such as trees, linked list, linked stack, linked queue and graphs
–Used for the dynamic memory allocation of a variable
example in c:
int * pnum;
int x;
pnum = &x;
Array
Array is a linear list is an elementary abstract data type that allows storage of elements of the same data type in the same contiguous memory area.
•A collection of similar data elements
•These data elements have the same data type (homogenous) •The elements of the array are stored in consecutive memory locations and are referenced by an index
•Array index starts from zero
•Declaration: •int arr[5]; •
•Accessing: •arr[0] = 7;
•arr[1] = 2;
•arr[2] = 13;
•arr[3] = 13;
•arr[4] = 13;
Linked list
•Linked list is a data structure that consists of a sequence of data records such that each record there is a field that contains a reference to the next record in the sequence.
•Linked list allows insertion and deletion of any element at any location.
•Linked list is used in many algorithms for solving real-time problems, when the number of elements to be stored is unpredictable and also during sequential access of elements.
•A linked list consists of two types: –Single Linked List –Double Linked List
Array: Linear collection of data elements, Store value in consecutive memory locations, Can be random in accessing of data •
Linked List: Linear collection of nodes, Doesn’t store its nodes in consecutive memory locations, Can be accessed only in a sequential manner
Single Linked List
Single linked list: Delete Algorithm
•To delete a value, first we should find the location of node which store the value we want to delete, remove it, and connect the remaining linked list.
• •Supposed the value we want to remove is x and assuming x is exist in linked list and it is unique. •
•There are two conditions we should pay attention to: if x is in a head node or, if x is not in a head node.
Double Linked List
Picture above is the visual of double linked list.
A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.
Advantages over singly linked list
1) A DLL can be traversed in both forward and backward direction.
2) The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
3) We can quickly insert a new node before a given node.
In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.