A list (リスト) is a data structure in which each element holds a pointer to the position of the next element, and these pointers chain the data into a single line.
Position
Data
Pointer (next position)
1 (head)
Apple
3
2
Grape
None (tail)
3
Orange
2
In the example, following the pointers from the apple at the head gives the orange and then the grape. Because the pointers set the order, it need not match the order of the stored positions. Adding or removing an element in the middle only means rewriting the pointers on either side, with no other element having to move.
AnalogyThink of a treasure hunt. The first clue tells you where the next clue is hidden, and following them one by one leads you to the end.
How to rememberPicture a list of names in which each row carries an arrow saying "next one is over here".
Exam points
Mix-upAn array (配列) places elements in consecutive positions and accesses them directly by index. A list (リスト) decides the next element through a pointer, so reordering or inserting does not require moving any element.
A stack (スタック) is a data structure that stores data as if piling it up and takes out the most recently added item first, which is called last in, first out (後入れ先出し, LIFO).
Push red
Push blue
Take out: blue
Take out: red
Taking out again removes the remaining red.
4 / 4
Storing an item is called a push and taking one out is called a pop, and both always happen at the single top position. The Back button in a web browser, which steps back through pages starting from the one you just viewed, is an everyday example of this behavior.
AnalogyThink of a pile of books on a desk. New books go on top and you also pick them up from the top, so the last book you put down is the first one you get back.
How to rememberThe word is the same stack as in haystack: a heap of things piled one on another.
Exam points
ExamThe next item taken out of a stack (スタック) is the one added most recently among the data stored at that moment.
ExamOf any two items sitting in a stack (スタック) at the same time, the one pushed later comes out first. No order of removal that breaks this rule can occur.
A queue (キュー) is a data structure that takes data out in the order it was stored, which is called first in, first out (先入れ先出し, FIFO).
Add red
Add blue
Take out: red
Take out: blue
Taking out again removes blue, which was next in line.
4 / 4
Data is added at the back of the line and taken out from the front. Storing an item is called an enqueue and taking one out is called a dequeue. A printer that handles incoming print jobs in order of arrival is one place this is used.
AnalogyThink of people waiting at a service counter. Newcomers join the end of the line, and the people who arrived first are called first.
How to rememberIn British English a queue is a waiting line, and to queue up is to join one.
Exam points
ExamThe k-th item taken out of a queue (キュー) is the k-th item that was stored. Adding data partway through never lets a later item overtake one that entered earlier.
Mix-upA stack (スタック) gives up its newest data first, while a queue (キュー) gives up its oldest. The difference lies not in how data is stored but in which end it is taken from.
A tree structure (木構造) is a data structure in which nodes (節) holding data branch out through parent-child links and connect in levels.
President
Sales Dept.
Sales Section 1
Sales Section 2
Development Dept.
Development Section
More nodes follow below, and each branch ends at a node with no children.
3 / 3
The top node with no parent is called the root, the end nodes with no children are called leaves, and every node other than the root has exactly one parent. The structure suits anything with a chain of command or containment, such as an organization chart or a folder hierarchy.
AnalogyThink of the folders on a computer. One folder can hold several folders, and each of those can hold more folders or files.
How to rememberIt is drawn as an upside-down tree, so the root sits at the top and the leaves at the bottom.
Exam points
Mix-upIn a list (リスト) each element links to at most one next element, whereas in a tree structure (木構造) one node can have several children below it.
Mix-upThe root (根) is the node with no parent, and a leaf (葉) is a node with no children. A tree has only one root but can have many leaves.
A binary tree (2分木) is a tree structure in which each node has at most two children, a left child and a right child.
Root
Left child
Leaf
Leaf
Right child
Leaf
The left and right children are treated as distinct, and a node may have just one child or none at all, as a leaf does. If values are stored by sending smaller ones to one side and larger ones to the other, for instance, fewer nodes need to be visited when searching for a target value.
AnalogyThink of a yes/no quiz chart. Each question leads on in at most two directions, yes and no; some questions continue on only one side, and some end there with a result.
How to remember"Binary" means two: picture a branch that forks into two.
Exam points
Mix-upThe "two" in binary tree (2分木) is the upper limit on the number of children. It does not mean every node has exactly two children.
Key points
Inserting into or deleting from a list is done by rewriting the pointers on either side, without moving any other element.
Among data sitting in a stack together, whatever was pushed later comes out sooner.
In a queue, the k-th item taken out is the k-th item that was stored.
In a tree structure, the top node with no parent is the root and nodes with no children are leaves, and a binary tree limits each node to two children or fewer.