ขอถามเกี่ยวกับ linked list ครับ

List มีหลายประเภทขึ้นอยู่กับ Implementation ซึ่งสองอย่างหลักๆที่นิยมใช้คือ Array List และ Linked List
ทั้ง Array List และ Linked List เป็น List เหมือนกัน เพราะงั้นสามารถใช้แทนกันได้เลย เพราะมี Operation เหมือนกัน ถ้าเป็นใน Java ทั้ง LinkedList และ ArrayList ใช้ Interface ร่วมกันคือ List เพราะฉะนั้นจะมี Method เหมือนกัน

ทีนี้มันจะต่างตรงเรื่องของ Performace ถ้าเราเข้าถึงข้อมูลตรงกลางของ List ด้วย Index แบบนี้ Array List จะเร็วเพราะสามารถคำนวณ Offset และกระโดดไปหาข้อมูลที่เราต้องการได้เลย ถ้าเป็น LinkedList เราต้องเดินนับทีละก้าวจากหัวของ List
ถ้าเราเข้าถึงข้อมูลที่หัวและท้ายอย่างเดียว และการเพิ่มหรือลบข้อมูลเกิดที่หัวและท้ายเท่านั้น แบบนี้ใช้ Linked List ได้ เพราะการเพิ่มและลดไม่มีข้อจำกัดเรื่องขนาดของ Memory ที่ต้องจองไว้ล่วงหน้าเหมือน Array List

Array List จะใช้หน่วยความจำติดกันทั้งหมด ถ้าเต็มแล้ว และเราต้องการเพิ่มข้อมูลใหม่เข้าไปอีก เราต้องจอง Array ใหม่ที่มีขนาดใหญ่กว่าเดิมและทำการคัดลอกข้อมูลจากที่เดิมมาที่ใหม่ ซึ่งปกติจะมีการจองเผื่อ เพราะไม่งั้นจะช้ามากที่ต้องคัดลอกข้อมูลทั้งหมดทุกครั้งที่มีการเพิ่มข้อมูล อย่างง่ายคือจองเผื่อเป็น 2 เท่าของแต่ก่อน และหากข้อมูลเหลือน้อยกว่าครึ่งก็จะคืนพื้นที่ไป เพราะงั้นขนาดที่จองก็จะเป็น 1, 2, 4, 8, 16, ...

ส่วน Linked List จะเป็นการเก็บ ข้อมูล และตำแหน่งของข้อมูลชุดถัดไป ซึ่ง Linked List ก็จะมีหลายแบบ
1. Singly Linked List
2. Doubly Linked List
3. Circular Singly Linked List
4. Circular Doubly Linked List

Single คือเก็บ Address ของตัวถัดไป เวลาหาข้อมูลก็จะเดินได้ทางเดียว
Doubly คือเก็บ Address ของตัวก่อนหน้าและตัวถัดไป ทำให้เดินได้สองทาง แต่จะใช้ขนาดพื้นที่มากกว่าเพราะต้องเก็บ Address
Circular คือหัวต่อหางเป็นวงกลม จากตัวสุดท้ายสามารถเดินมาต่อที่ตัวแรกได้