Kump 3 chapter 2 - Coggle Diagram
Kump 3 chapter 2
- a linked list is 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
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
Basic concept of linked list
- A linked list is an ordered series of connected data / nodes
- Each element of the linked list has
a. Some data
b. A link to the next element
c. The link is used to chain the data
- Linked lists are a dynamic data structure, allocating the needed memory while the program is running.
I- nsertion 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.
- 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
Type of linked list :
- a. Single linked list
- b. Double linked list
- c. Circular linked list
- d. Circular double linked list
a. 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
A single linked list whose nodes contain two fields: an integer value and a link to the next node
b. 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').
A double linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node
c. 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‘
d. 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 ListBasic operation of linked list:
- Creation - Create one new linked list.
- Create node - To create one new source for connecting items in the linked list.
- Check the linked list -Check if the linked list is empty.
- insertion - Add an item in the linked list.
- Deletion - Delete one item from the linked list.
- Traversing- Delete one item from the linked list.
DECLARING LINKED LIST
CREATE HEAD & NODE
- a list or sequence is 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
- List is a collection of data, element, component or objects with similar data type
- 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.
Using array as a list
- An array is 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.
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.
Characteristic of LIST :
- Maximum size
- Array for storing entries
- number of elements/entries
- Current possittion
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
- Another operation involved in implementing list using array are created list.
- For create list operation , just declare an array.
- int listNumber[maxSize]; // declaration of an array
- int NoOfItem; // used to store no. of item in an array