03_Handout_1(6).pdf

IT1815 Linked Lists It can grow and shrink The array size is specifi...

IT1815 Linked Lists It can grow and shrink The array size is specified during program execution. during declaration. Linked List Basics The position of the elements The position of the elements A linked list is used for storing a collection of data where each is allocated during runtime. is allocated during element is a separate object. compilation. Elements in a linked list are called nodes. Elements are sequentially Elements are randomly The parts of a node are the following: accessed. accessed. Data Pointer It utilizes memory efficiently. Memory utilization is o Data field – This contains the value of the element. ineffective. o Pointer field (link or reference) – This contains the address (random memory location) of the next node. Types of Linked List The next node in the list is referred to as the successor. Singly linked list – the basic linked list The first node in the list is called head. Doubly linked list – contains an extra pointer to connect to The last node points to null since there are no more the previous node in the sequence. The left pointer contains successive elements. the address of the preceding node called “predecessor.” Left Pointer Data Right Pointer A linked list is illustrated by: o Placing the address of the node above its data field o Placing the address of the next node in the node’s A doubly linked list is illustrated by: pointer field o Placing the address of the node above its data field o Indicating null in the pointer field of the last node o Placing the address of the preceding node in the o Connecting the previous node to the next node using node’s left pointer field an arrow to the right. o Placing the address of the next node in the node’s Operations of a linked list: right pointer field o Display – shows the elements in the list o Indicating null in the left pointer field of the first node o Insert – adds an element into the list and in the right pointer field of the last node. o Delete – removes a specific element or all the Circular linked list is a linked list in which the last node’s right elements from the list pointer contains the address of the first node. o Search – finds a specific element in the list o Count – returns the number of elements in the list Linked List versus Array Iteration is the process of repeating a set of instructions. This References: Karumanchi, N. (2017). Data structures and algorithms made easy. Hyderabad: is also known as “looping.” CareerMonk Publications. Linked List Array TechDifferences (n.d.). Differences between array and linked list. Retrieved from https://techdifferences.com/difference-between-array-and-linked-list.html The number of elements The number of elements is can expand. fixed upon creating the array. 03 Handout 1 *Property of STI  [email protected] Page 1 of 1