Scribd
Upload
1 views2 pages

data_structures_notes

Detailed class notes on arrays and linked lists for a data structures course. Covers properties, use cases, and Python implementations, with time complexity analysis and practice problems. Suitable for computer science students learning fundamental data structures.

Uploaded by

silivom177
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
1 views2 pages

data_structures_notes

Detailed class notes on arrays and linked lists for a data structures course. Covers properties, use cases, and Python implementations, with time complexity analysis and practice problems. Suitable for computer science students learning fundamental data structures.

Uploaded by

silivom177
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Data Structures and Algorithms: Class Notes (Arrays and Linked Lists)

Introduction
Data structures organize data for efficient access and modification. This lecture covers
arrays and linked lists, fundamental structures in computer science.

Arrays
Arrays store elements of the same type in contiguous memory locations, enabling fast
access via indices.
• Properties:
– Fixed size, defined at creation.
– Constant-time access: O(1) for reading/writing by index.
– Insertion/deletion is O(n) due to shifting elements.
• Use Cases: Storing lists, matrices, or lookup tables.
Example: Array in Python
# Initialize and access array
numbers = [10, 20, 30, 40]
print(numbers[2]) # Output: 30
numbers.append(50) # Dynamic arrays in Python (lists)

Linked Lists
Linked lists consist of nodes, each containing data and a reference to the next node.
• Properties:
– Dynamic size, grows/shrinks as needed.
– O(1) insertion/deletion at head, O(n) at arbitrary positions.
– O(n) access time, as nodes are non-contiguous.
• Types: Singly linked (one direction), doubly linked (two directions).
• Use Cases: Implementing stacks, queues, or dynamic data storage.
Example: Singly Linked List in Python
class Node:
def __init__(self, data):
self.data = data
self.next = None

class LinkedList:
def __init__(self):
self.head = None

def append(self, data):


new_node = Node(data)
if not self.head:
self.head = new_node
return
current = self.head

1
while current.next:
current = current.next
current.next = new_node

# Create and populate linked list


ll = LinkedList()
ll.append(1)
ll.append(2)

Comparison
• Arrays are better for random access and fixed-size data.
• Linked lists excel in frequent insertions/deletions and dynamic sizing.

Practice Problems
1. Implement a function to reverse an array in-place.
2. Write a method to detect a cycle in a linked list.

Further Reading
Study time complexity (Big-O notation) and explore dynamic arrays (e.g., Python lists vs.
fixed arrays).

You might also like