Data Structure - 4 Pointer & Linked List

Data Structure - 4 Pointer & Linked List

• 1.
  Department of Informatics Facultyof Industrial Engineering Universitas Pembangunan Nasional “Veteran” Yogyakarta Data Structure Andi Nurkholis, S.Kom., M.Kom. Pointer & Linked List September 8, 2025
• 2.
  Introduction of Pointer& Linked List Pointer is an important concept in programming, particularly in C and C++, storing the memory address of data and enabling efficient memory management. This concept forms the basis for creating dynamic data structures such as linked list, which are composed of nodes connected by pointer. Unlike array, which are stored sequentially in memory, linked list can resize as needed, making them more flexible for data storage and manipulation.
• 3.
  Concept of Pointer 1. PointerDefinition 2. Pointer Declaration 3. Pointer Usage 4. Pointer Benefits 5. Pointers in Data Structures
• 4.
  Definition of Pointer Pointeris a variable that stores the memory address of another variable. By using pointers, we can access and manipulate data in memory without having to duplicate that data. Pointer is special variables in programming languages like C and C++ that are used to store the memory address of another variable. ü Regular variables store data values (e.g., int x = 10; → x stores 10). ü Pointers store the memory address where the data is stored (e.g., int *p = &x; → p stores the memory address of x).
• 5.
  Declaration of Pointer Pointermust be declared before they can be used. To declare a pointer, use an asterisk (*) before the pointer name. Example: int *ptr; // Pointer to store the address of an integer variable Important note: ü data_type ensures that the pointer can only be used to point to the address of a variable of that type. ü Uninitialized pointers should not be used because their values are arbitrary and can cause runtime errors.
• 6.
  Use of Pointer üGetting a Variable Address: To get the address of a variable, we use the & operator. int a = 5; int *ptr = &a; // The pointer ptr stores the address of the variable a ü Accessing Values Through Pointer: To access and manipulate the value pointed to by a pointer, we use the * operator (dereferencing operator). printf("%d", *ptr); // Display the value of a through the pointer *ptr = 10; // Change the value of a to 10
• 7.
  Benefit of Pointer üDynamic Memory Management: Pointers allow programs to allocate and free memory at runtime using functions like malloc(), calloc(), and free(). This is important for data whose size is unknown at compilation. ü Building Complex Data Structure: Data structures like linked lists, stacks, queues, trees, and graphs are built using pointers to connect one element to another. ü Data Processing Efficiency: Pointers allow functions to pass memory addresses rather than copying the entire data, saving time and memory space (pass by reference).
• 8.
  Benefit of Pointer üIndirect Data Manipulation: Pointers allow variable values to be changed from outside the scope of a function or program block. ü Interaction with Hardware and the Operating System: Pointers are used to access specific memory addresses, which is fundamental to systems programming, buffer management, and hardware communication.
• 9.
  Pointer in DataStructure In Data Structure, pointer is key element for: ü Linked List: Each node stores a pointer to the next node. ü Tree: Each node stores a pointer to its left and right child. ü Graph: Pointers are used to connect nodes in an adjacency list. ü Dynamic Array: Pointers are used to refer to blocks of memory that can be expanded or reduced.
• 10.
  Concept of Linked List 1.Definition of a Linked List 2. Types of Linked Lists 3. Advantages of Linked List over Array
• 11.
  Definition of LinkedList Linked list is a dynamic data structure consisting of a collection of elements called nodes, where each node stores data and a pointer (or link) that points to the next node (or other nodes, depending on the type). Unlike arrays, which store elements contiguously in memory, linked list stores elements in memory locations that are not necessarily sequential but are connected via pointers. Node Structure in a Linked List: Each node in a linked list typically consists of two parts: ü Data: Stores a value or information. ü Pointer: Points to the next node.
• 12.
  Types of LinkedList There are three types of Linked List: ü Singly Linked List: Each node only has a pointer to the next node. ü Doubly Linked List: Each node has two pointers: one to the next node and one to the previous node. This allows forward and backward traversal. ü Circular Linked List: The last node points back to the first node, making the list circular.
• 13.
  Linked List &Array Advantages of Linked List over Array: ü Dynamic Size: Can grow or shrink as needed without having to specify the size upfront. ü Fast Insertion and Deletion: Insertion/deletion operations at the beginning or middle of a list simply require modifying the pointer without moving other elements. ü Efficient Memory Usage: Memory is allocated only when needed, without having to reserve large blocks at once as with arrays.
• 14.
  Linked List &Array ü Reduced Memory Fragmentation: No need for contiguous memory blocks; each node can be placed in a different memory location. ü Data Structure Flexibility: Facilitates the creation of complex data structures such as stacks, queues, deques, graphs, and trees. ü Ease of Data Reorganization: Changes in the order of elements can be made simply by modifying pointers without copying the entire list.
• 15.
  Basic Operations of LinkedList 1. Linked List Initialization 2. Adding Elements (Insertion) 3. Removing Elements (Deletion) 4. Traversing a Linked List
• 16.
  Advantages of LinkedList ü Size Flexibility: Linked lists can be easily expanded without size limitations, adapting to the number of elements needed. ü Efficient Insertion and Deletion: Adding and deleting elements can be done quickly without the need to move other elements.
• 17.
  Disadvantages of LinkedList ü Slower Access: The access time to find a specific element is slower than with arrays (O(n)). ü Additional Memory Usage: Because each node requires storage for a pointer, memory usage can be higher than with arrays. ü Implementation Complexity: Linked lists are more complex to implement and understand than arrays.
• 18.
  Department of Informatics Facultyof Industrial Engineering Universitas Pembangunan Nasional “Veteran” Yogyakarta Andi Nurkholis, S.Kom., M.Kom. September 8, 2025 Done Thank You