連結リスト
【英】linked list
連結リストとは、データ構造の一種であるリストの中で、自分の次、および、前の要素を示す情報（リンク情報）を持つことで、要素を連結（リンク）させたリストのことである。
リストは、データの要素を順番に並べて扱うデータ構造のことである。
次の要素へのリンクしか持たない連結リストのことを単方向（一方向）リスト、次と前への要素へのリンクを持つものを双方向リストと言うこともある。
連結リストは配列とは違い、リンクを辿らないと各々の要素にアクセスができず、また、リンクのためのメモリを余分に持つ必要があるなど不利な点がある。しかし、データの個数が前もってわからないような場合や、データの追加や削除が頻繁に発生するような場合などの扱いには適している。
連結リスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/07 16:50 UTC 版)
- ^ “RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE (Part I) (12-May-1998)”. www-formal.stanford.edu. 2024年4月7日閲覧。
- ^ “McCarthy et al. LISP I Programmer's Manual. — Software Preservation Group”. softwarepreservation.org. 2024年4月7日閲覧。
- ^ a b Preiss, Bruno R. (1999年), Data Structures and Algorithms with Object-Oriented Design Patterns in Java, Wiley, p. page 97, 165, ISBN 0471-34613-6
- ^ 最後尾へのリンクを保持していれば O(1) だが、最後尾を探すために先頭から辿る必要がある場合は O(n)
連結リスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/16 13:57 UTC 版)
PDP-8での連結リストの実装例。 GETN, 0 /Gets the number pointed to and moves the pointer CLA CLL /Clear accumulator TAD I PTR /Gets the number pointed to DCA TEMP /Save current value ISZ PTR /Increment pointer TAD I PTR /Get next address DCA PTR /Put in pointer JMP I GETN /return PTR, 0 TEMP, 0
※この「連結リスト」の解説は、「PDP-8」の解説の一部です。
「連結リスト」を含む「PDP-8」の記事については、「PDP-8」の概要を参照ください。
連結リスト
- 連結リストのページへのリンク
