Please enable JavaScript.
Coggle requires JavaScript to display documents.
CHAPTER2 : LIST AND LINKED LIST, definition, disadvantages, advantages,…
CHAPTER2 : LIST AND LINKED LIST
LIST
an abstract data structure that implements an ordered collection of values, where the same value may occur more than once
value is often called an item, entry or element of the list
Definition
List is a linear data structure, which contains a sequence of elements. The list has the property length (count of elements) and its elements are arranged consecutively.
List is a collection of data, element, component or objects with similar data type
Using array as a list
a series of elements of the same type placed in contiguous memory locations that can be individually referenced by adding an index to a unique identifier.
Example: We can store 5 values of type int in an array without having to declare 5 different variables, each one with a different identifier. Instead of that, using an array we can store 5 different values of the same type, int for example, with a unique identifier.
EXAMPLE OF LIST
CHARACTERISTIC OF LIST
LIST OPERATION
Insertion
can be made at the beginning of the list, in the middle of the list or at the end of the list
Deletion
requires that the list be searched to locate the data being deleted
Retrieval
requires that data be located in a list and presented to the calling module without changing the contents of the list
Traversal
is a special case of retrieval in which all elements are retrieved in sequence
Another operation involved in implementing list using array are createList .
For createList operation, just declare an array.
Example, if want to create a list of 10 numbers, it can be declared as
-#define maxSize 10 // used to declare maximum size of array
-int listNumber[maxSize]; // declaration of an array
-int NoOfItem; // used to store no. of item in an array
LINKED LIST
data structure that consists of a sequence of data records such that in each record there is a field that contains a reference to the next record in the sequence
benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk.
-linked lists allow insertion and removal of nodes at any point in the list
EXAMPLE OF LINKED LIST
BASIC CONCEPT OF LINKED LIST
an ordered series of connected data / nodes
Each element of the linked list has
Some data
A link to the next element
The link is used to chain the data
EXAMPLE
Differences between List & Linked List
List
Static size of list.
Add and delete item required more steps.
Suitable for simple list.
Easy programming processes
Easy program update.
Low of memory and computerizing time.
Linked List
Dynamic size of list.
Add & delete item required less steps.
Suitable for larger list.
Complex programming processes.
Complicated program update
High of memory and computerizing time.
Advantages of Linked List
Linked lists are a dynamic data structure, allocating the needed memory while the program is running.
Insertion and deletion node operations are easily implemented in a linked list.
Does not require any extra space therefore it does not waste extra memory
They can reduce access time and may expand in real time without memory overhead.
Disadvantages of Linked List
They have a tendency to use more memory due to pointers requiring extra storage space.
Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list.
Not suitable for simple list with minimal size
TYPES OF LINKED LIST
Single linked list
contain nodes which have a data field as well as 'next' field,which points to the next node in line of nodes
Double linked list
each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').
Circular linked list
In the last node of a list, the link field often contains a null reference, a special value used to indicate the lack of further nodes.
A less common convention is to make it point to the first node of the list; in that case the list is said to be 'circular' or 'circularly linked‘
Circular double linked list
Doubly Circular linked list has both the properties of doubly linked list and circular linked list.
Two consecutive elements are linked by previous and next pointer and the last node points to first node by next pointer and also the previous pointer of the head node points to the tail node.
OPERATION IN LINKED LIST
Basic operations of linked list
-Creation
-Insertion
-Deletion
-Traversing
OPERATION IN LINKED LIST : DECLARING LINKED LIST
OPERATION IN LINKED LIST: CREATE HEAD & NODE
OPERATION IN LINKED LIST: INSERT
OPERATION IN LINKED LIST: DELETE
1.CREATE LINKED LIST
-create one new linked list.
2.CREATE NOTE
-to create one new source for connecting items in the linked list.
3.CHECK THE LINKED LIST
-check if the linked list is empty
4.INSERT NODE IN THE LINKED LIST
-add an item in the linked list
5.DELETE NODE IN THE LINKED LIST
-delete one item from the linked list
6.TRAVERSING
-to find a value find a position for insertion,etc
LINKED LIST STRUCTURE
definition
disadvantages
advantages
differences
4 types of linked list
