Linked Lists

Overview of Computer Memory

• Random Access Memory (RAM): Temporary storage that resets when the computer is turned off.

  • Used by programs to store information as needed.

  • Measurement units include bytes, kilobytes, megabytes, gigabytes, terabytes, etc.

Memory Representation

• Bytes: A sequence of eight bits; the smallest unit used to store data.

• Character Storage:

  • Examples: characters, strings, integers, floats, and complex objects.

  • A record could contain a name, thread, and birthdate.

Memory Addressing

• Representation of memory where each cell is a byte and has an address.

  • Each cell can be individually addressed or referenced.

Storing Characters

• Example: The character 'C' is stored as its ASCII value (99) in binary (01100011).

  • Actual character is not stored, just the binary representation in memory.

Storing Integers

• Memory Usage Example: Storing the integer 275 requires two bytes because its binary representation (000000100010011) needs 9 bits.

  • Longer numbers, such as 20 million, may need four bytes.

Arrays vs. Linked Lists

• Arrays:

  • Fixed size; need to allocate space for the known number of integers, e.g., 10 integers require 20 bytes.

  • Contiguous memory allocation: all integers stored directly next to each other.

  • If more than allocated are needed, the program can overwrite remaining memory unintentionally.

Array Limitations

• Cannot dynamically grow or shrink.

• Must manage memory carefully; exceeding allocated spots can lead to memory issues.

Linked Lists

• Dynamic Structure:

  • Can grow or shrink as needed, allocating memory for each new element as a node.

  • Elements stored in nodes, which are not contiguous in memory, linked by references.

Nodes and References

• Each node contains:

  • An element (data)

  • A reference to the next node in the sequence.

• Traversal starts from the first node, with each node leading to the next until it points to nothing (end of the list).

Implementation Example

• The last node points to nothing, denoted as null, nil, or none, depending on programming language.

• Can store different types and structures, as nodes contain references to locations where data is stored instead of the data itself.

Benefits and Challenges of Linked Lists

• Advantages:

  • Flexibility: able to grow/shrink without predetermined size.

  • Can contain diverse types of data, not limited to one type.

• Disadvantages:

  • Requires traversal to access elements, making access to specific elements slower than arrays.