• A list of data that are linked or chained in a linear fashion
  • Each element in it (except the last one) will be followed by another one
• Each data is kept in a node and each node has an information of which node is next to it.
  • ง่าย ๆ ก็คือมันเก็บ ข้อมูล (ตัวเลข, ตัวหนังสือ) และ ตัวไหนอยู่ต่อไป

Arrays VS Linked Lists

• With an array, we view all the elements as being grouped together, sitting in one block of memory.
• With a linked list, each element sits separately in its own block of memory. We call this small separate block of memory a “node.”

Simple Singly Linked List (SList)

• Compose of nodes that keep data
• Each node is linked to its next neighbor in one direction
• The front and the rear of SList is called head and tail, respectively.

Meta Data

• The first node, the last node, and size are frequently used in most SList’s operations and applications.
  • Thus, the information about them are normally specially for fast access.
• These additional information is called meta data.

SList Operations

ดู Java Code ได้ที่ SList

• addFirst: Add a new item at the front most
• addLast: Add a new item at the rear most
• addAtIndex: Add a new item at a specific index $(0,\dotso,n)$
• removeFirst: Remove an item at the front most and return the deleted item
• removeLast: Remove an item at the rear most and return the deleted item
• removeAtIndex: Remove an item at a specific index $(0,\dotso,n)$ and return the deleted item
• get: get and return a value at index
• set: set a value at index

SList Complexity