Advanced Programming and Applications

Data structures: array, linked list, stack, queue

A data structure is a way to arrange data so a program can use it fast and easily.

• Array: fixed size, items sit side by side, any item can be reached by its index (a[3]). Adding in the middle is slow.
• Linked list (dynamic): each node stores a value and a link to the next node. It grows and shrinks as needed, but to reach item 5 you must walk through items 1 to 4.
• Stack: push and pop at one end only (LIFO). Used for undo, back button and checking brackets.
• Queue: add at the back, remove from the front (FIFO). Used for print jobs and waiting lines.

Libraries already contain these tools. In Python a list works as a stack (append, pop), and collections.deque works as a fast queue. Use a library when it exists; do not rewrite it.

stack = []
stack.append(5); stack.append(8)
stack.pop()      # gives 8
from collections import deque
q = deque([4, 9]); q.append(2)
q.popleft()      # gives 4

Using an IDE: write, run, test

An IDE (integrated development environment) puts an editor, a run button, a debugger and tools in one place. It colours your code, suggests names, and shows errors as you type.

• Run the program and read the output.
• Test with easy, normal and tricky inputs (an empty list, zero, a very big number).
• Debug: set a breakpoint and step line by line to watch the variables.

2D and 3D visualisation and animation

Pictures help us see patterns. Programs can draw charts (bar, line, scatter), 2D drawings and 3D scenes. An animation is the same picture drawn again and again with a small change each time (about 30 to 60 times a second). A simple way: keep a variable such as x, add a little to it each frame and redraw. The 3D on this page is made the same way, with a 3D library.

Advanced spreadsheet functions

Spreadsheets can do program-like work with functions:

• IF(B2>=50,"Pass","Fail") chooses between two results.
• SUMIF(B2:B5,">=50") adds only the cells that match a rule; COUNTIF counts them.
• VLOOKUP(2, A2:B5, 2, FALSE) looks for 2 in the first column and returns the value from column 2 of the same row. XLOOKUP does the same more easily.
• Pivot tables sum up large data by groups, and charts show the result.

Relational databases and SQL

A relational database keeps data in tables of rows and columns. Each table has a primary key, a column whose values are unique (the id). Another table uses that value as a foreign key to link back. Good design stores each fact once, so there is no repeated data.

SQL is the language for asking questions and changing data:

SELECT name, score FROM students
JOIN marks ON students.id = marks.id
WHERE score >= 50 ORDER BY score DESC;

INSERT INTO marks (id, score) VALUES (5, 67);
UPDATE marks SET score = 55 WHERE id = 2;
DELETE FROM marks WHERE id = 5;

Integrity means the data stays correct: keys are unique, a foreign key must match a real row, and values must have the right type. Security means passwords for users, giving each user only the rights they need, backups, and never building SQL by joining user text into the query (use parameters), which stops SQL injection.

Contributing to open resources

Many tools and libraries are open source: anyone can read, use and improve them under a licence. You can help by fixing a bug, improving a guide, translating a page or adding an example. Always read the licence, give credit, and write clear, polite messages when you suggest a change.

Try it

In the 3D step 5, push 3 items on a stack, then pop them. Write the order. Do the same with a queue. Then predict first, check second: after adding 4, 9, 2 and removing one item, which value is left at the front of the queue and at the top of the stack?

Key formulas and definitions

• Stack = LIFO (last in, first out): push, pop.
• Queue = FIFO (first in, first out): enqueue, dequeue.
• Array: fixed size, access by index. Linked list: dynamic size, follow links.
• SELECT columns FROM table WHERE condition
• Primary key = unique id. Foreign key = link to another table.

Worked examples

Common mistakes

• Using an array when the size is not known in advance. A list or linked list is better.
• Mixing up stack and queue. Stack removes the newest; queue removes the oldest.
• Forgetting WHERE in UPDATE or DELETE, which changes every row.
• Building SQL by joining user text into a string. Use parameters instead.