Linked Lists

linktr.ee/bingacm

How to Store Data?

• Put all in one place, order sequentially
• Arrays!
• Static memory
• Easy to search and reverse
• Difficult to add/remove elements
• What if we don’t know how many to add? Lots of anticipated changes ?
• Make memory dynamic, so elements are not close together
• Each element knows where the next element is located

Linking Elements (Single)

• Start with one element at a specific address (i.e. 0xABCD)
• Think of each element as a flashcard, containing two things:
• It’s data (a string, an int, a char, etc.)
• The address of another element (0x####)
• Last element contains NULL instead of next address
• Head = first

Linked Lists

• Two basic types of linked lists
• Singly Linked
• Doubly Linked
• A few more versions exist, different uses
• Advantages:
• Adding, Deletion, Memory, Dynamic
• Disadvantages:
• Searching, Organization, Reversal �

Activity Break (Link, Add, Delete)

Why Linked Lists ?

• Problems where adding and deleting happen MORE than searching for a specific element!
• Dynamic saves memory with changes

​

Which Linked Lists?

• Singly Linked
• Single + Tail
• Single + Circular
• Doubly Linked

Activity Break (Searching, Reversal)

Coding: Node Class

Coding: Linked List Class

Applications for Linked Lists

LeetCode: Problem 2�

Add Two Numbers

342 + 465 = 807

Solution (c++)

�LeetCode: Problem 21

​

Merge 2 Sorted Linked Lists

Solution (in Java)

LeetCode: Problem 725

Split Linked List into parts

Solution (c++)

Thanks for coming :)