หลักการ ของ วีลิสต์

แทนที่จะโยงต่อกันด้วยโหนดตัวเดียวแบบในรายการแบบโยง วีลิสต์ใช้การโยงของก้อนข้อมูล (memory block) ซึ่งประกอบด้วยอาเรย์ซึ่งสามารถเก็บข้อมูลได้หลายตัวมาโยงต่อกัน โดยมีฐาน (base) เป็นตัวชี้ (pointer) ไปยังก้อนข้อมูลก่อนหน้า และมีออฟเซ็ต (offset) เป็นตัวอ้างอิงตำแหน่งปัจจุบันของข้อมูลที่เทียบจากรายการ และตำแหน่งล่าสุด (last used) ซึ่งเทียบตำแหน่งของข้อมูลจากอาเรย์ปัจจุบันที่ข้อมูลตัวนั้นอยู่ นอกจากนี้ในก้อนข้อมูลยังมีตัวแปรเก็บขนาดสูงสุดของอาเรย์ปัจจุบัน และทุกๆครั้งที่ข้อมูลเต็มก้อนข้อมูลอันเก่า เมื่อเพิ่มก้อนข้อมูลใหม่ ก้อนข้อมูลใหม่จะมีขนาดเป็น r เท่าของก้อนข้อมูลเดิม และก้อนข้อมูลก่อนๆจะมีขนาดลดลงเป็น r เท่า

การเพิ่มข้อมูล

ในการเพิ่มข้อมูลเข้าที่ตำแหน่งหน้าสุดของวีลิสต์ (ตำแหน่งสุดท้ายของรายการ) จะต้องตรวจสอบว่าอาเรย์ของข้อมูลในก้อนข้อมูล (memory block) ปัจจุบันนั้นเต็มรึยัง ถ้าไม่เต็มก็เพิ่มข้อมูลลงในตำแหน่งถัดไป และเพิ่มค่าของตำแหน่งล่าสุด (last used) ในก้อนข้อมูลปัจจุบัน ถ้าอาเรย์ของข้อมูลเต็มแล้วต้องทำการสร้างก้อนข้อมูลตัวใหม่ที่มีอาเรย์เป็นขนาด r เท่าของก้อนข้อมูลตัวเดิม แทรกเข้าไปที่ตำแหน่งหน้าของก้อนข้อมูลตัวก่อน (ตำแหน่งท้ายสุดของรายการ) และให้ออฟเซ็ต (offset)ของก้อนข้อมูลตัวล่าสุดเก็บตำแหน่งสุดท้ายของรายการจากก้อนข้อมูลอันก่อน

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

การลบข้อมูล

ในการลบข้อมูลจากตำแหน่งหน้าสุดของวีลิสต์ (ตำแหน่งท้ายสุดของรายการ) ทำได้โดยลบตำแหน่งล่าสุด (last used) ที่อ้างอิงอาเรย์ของข้อมูลลงหนึ่งค่า ซึ่งการลบข้อมูลด้วยวิธีนี้จะไม่คืนหน่วยความจำที่จองไว้ แต่เมื่อมีการเพิ่มข้อมูลตัวใหม่จะเขียนทับตำแหน่งเดิม เมื่อตำแหน่งอ้างอิงของอาเรย์ข้อมูลในก้อนข้อมูลปัจจุบันมีค่าติดลบ การให้ตัวชี้ชี้ไปยังก้อนข้อมูล (memory block) ถัดไป ก้อนข้อมูลที่ถูกลบนั้นจะถูกเก็บกวาดด้วยตัวเก็บขยะ (Garbage Collection)

ในการลบข้อมูลที่ตำแหน่งใดๆที่ไม่ใช่ตำแหน่งหน้าสุดต้องมีการสร้างวีลิสต์ตัวใหม่ให้ชี้ไปยังข้อมูลตำแหน่งก่อนหน้าข้อมูลที่จะทำการลบ แล้วเพิ่มข้อมูลจากวีลิสต์ตัวเก่าโดยไม่เพิ่มข้อมูลจากตำแหน่งที่ต้องการลบ

การเข้าสู่ตำแหน่งใดๆ

การเข้าสู่ตำแหน่งที่ n ใดๆของวีลิสต์ จะเริ่มด้วยการนำ n ลบกับออฟเซ็ต (offset) ของก้อนข้อมูลปัจจุบันถ้าเป็นบวก แสดงว่าตำแหน่งนั้นอยู่ที่ตำแหน่งของอาเรย์ตำแหน่งที่ n - offset ถ้า n ลบกับออฟเซ็ตเป็นลบ แสดงว่าตำแหน่งนั้นอยู่ในอาเรย์ข้อมูลของก้อนข้อมูล (memory block) ถัดๆไป ซึ่งเราสามารถหาได้โดยลบกับออฟเซ็ตของก้อนข้อมูลถัดไปๆ เรื่อยๆ จนลบแล้วได้ค่าของ n ลบกับออฟเซ็ตแล้วเป็นบวก ตำแหน่งนั้นคือตำแหน่งของอาเรย์ที่ n - offset ของก้อนข้อมูลตัวนั้น