ค่าต่าง ๆ ถูกใส่ที่ปลายของแถวลำดับพลวัต เมื่อข้อมูลเต็มความจุแล้วจะมีการขยายความจุโดยมีการเพิ่มขนาดเป็นอัตราเรขาคณิต (ในที่นี้คือเพิ่มทีละ 2 เท่า) ช่องสีเทาแสดงถึงพื้นที่ที่ไม่มีการใช้งาน การเพิ่มข้อมูลส่วนใหญ่ใช้เวลาคงที่ ในขณะที่การเพิ่มบางครั้งต้องมีการขยายความจุ ซึ่งใช้เวลา Θ ( n ) {\displaystyle \Theta (n)} (มีรูปเต่ากำกับ) ขนาดและความจุได้แสดงให้เห็นไว้ในรูปภาพแล้ว

แนวคิดเบื้องต้นของแถวลำดับพลวัตเริ่มต้นด้วยการจองหน่วยความจำพลวัตเพื่อสร้างแถวลำดับขนาดคงที่ขึ้นมาให้มีขนาดในระดับหนึ่ง เรียกขนาดนี้ว่าความจุของแถวลำดับพลวัต แถวลำดับที่สร้างมานี้จะประกอบไปด้วยสองส่วนคือ ส่วนที่เก็บข้อมูลของแถวลำดับพลวัต กับ ส่วนที่ไม่ได้ใช้งาน ขนาดของส่วนที่เก็บข้อมูลนี้เรียกว่าขนาดของแถวลำดับพลวัต เมื่อมีการเพิ่มข้อมูลเข้ามาต่อท้ายก็เป็นเพียงการเปลี่ยนส่วนที่ไม่ได้ใช้งานให้มาเป็นส่วนเก็บข้อมูล ในขณะที่การลบข้อมูลออกด้านท้ายก็เป็นการเปลี่ยนส่วนเก็บข้อมูลให้มาเป็นส่วนที่ไม่ได้ใช้งาน ซึ่งการดำเนินการเปลี่ยนพื้นที่ไปมาระหว่าง ส่วนที่เก็บข้อมูล กับ ส่วนที่ไม่ได้ใช้งาน ใช้เวลาคงที่หรือ Θ ( 1 ) {\displaystyle \Theta (1)} เท่านั้น

ตราบใดที่ขนาดของแถวลำดับพลวัตมีค่าน้อยกว่าหรือเท่ากับความจุของแถวลำดับพลวัตก็จะไม่มีปัญหาใด ๆ เกิดขึ้น แต่ถ้าหากเกิดเหตุการณ์ที่มีการเพิ่มข้อมูลจนทำให้ขนาดของแถวลำดับพลวัตมีค่าเกินความจุของแถวลำดับพลวัต สิ่งที่ต้องทำก็คือการขยายความจุ โดยการสร้างแถวลำดับขนาดคงที่อันใหม่ให้มีขนาดมากกว่าเดิม (มีความจุมากกว่าความจุเดิม) และคัดลอกข้อมูลจากแถวลำดับขนาดคงที่อันเดิมไปแถวลำดับขนาดคงที่อันใหม่ การดำเนินการขยายความจุนี้เสียเวลามาก กล่าวคือหากมีข้อมูลอยู่ n {\displaystyle n} ตัวในแถวลำดับพลวัต การขยายความจุนี้จะใช้เวลาเชิงเส้น หรือ Θ ( n ) {\displaystyle \Theta (n)}

รูปแบบการทำงานของแถวลำดับพลวัต อาจแบ่งได้ออกเป็น 3 แบบ คือ

1. การทำงานที่ทราบจำนวนของข้อมูล วิธีนี้มีประสิทธิภาพดีมาก แต่จำเป็นต้องทราบจำนวนข้อมูล อาจไม่เหมาะในการใช้งานบางกรณี
2. การทำงานที่ไม่ทราบจำนวนของข้อมูล - เพิ่มความจุเป็นค่าคงที่ วิธีนี้ไม่ค่อยมีประสิทธิภาพ จึงไม่มีการนำมาใช้งานจริง
3. การทำงานที่ไม่ทราบจำนวนของข้อมูล - เพิ่มความจุเป็นอัตราเรขาคณิต วิธีนี้ให้ผลลัพธ์เทียบเท่ากับการทำงานที่ทราบจำนวนของข้อมูล มีประสิทธิภาพดีมาก และยังไม่มีข้อจำกัดเรื่องจำนวนข้อมูล เป็นแถวลำดับพลวัตที่นิยมใช้โดยทั่วไป

การทำงานที่ทราบจำนวนของข้อมูล

ในกรณีที่ทราบว่าแถวลำดับพลวัตจะเก็บข้อมูลเท่าใด สามารถกำหนดความจุให้เป็นค่าคงที่หนึ่งที่มีค่ามากกว่าหรือเท่ากับจำนวนของข้อมูล เพื่อรับประกันว่าจะไม่มีปัญหาที่ขนาดของแถวลำดับพลวัตมีค่าเกินความจุของแถวลำดับพลวัต ซึ่งนำไปสู่การเสียเวลาจากการขยายความจุ นอกจากนี้ เนื่องจากความจุเป็นค่าคงที่ พื้นที่ที่สูญเสียไปโดยไม่จำเป็นก็เป็นค่าคงที่เช่นเดียวกัน อย่างไรก็ตาม ในทางปฏิบัติมักจะไม่รู้ถึงจำนวนของข้อมูลที่แน่นอน และการเก็บข้อมูลด้วยแถวลำดับพลวัตที่ความจุเป็นค่าคงที่ในบางสถานการณ์ กลับทำให้สูญเสียพื้นที่โดยไม่จำเป็นอย่างมากมาย เช่นหากมีข้อมูล n {\displaystyle n} ตัวที่จะนำมาเก็บบนรายการ m {\displaystyle m} รายการตามคำสั่งที่กำหนด จะได้ว่ารายการหนึ่ง ๆ มีโอกาสที่จะมีข้อมูลมากสุดถึง n {\displaystyle n} ตัว ดังนั้นหากใช้แถวลำดับพลวัตที่ความจุเป็นค่าคงที่ในการทำรายการทั้ง m {\displaystyle m} รายการนั้น ก็ต้องหน่วยความจำถึง Θ ( n m ) {\displaystyle \Theta (nm)} เพื่อรับประกันว่าข้อมูลจะสามารถเก็บได้หมด แต่ถ้าหากใช้แถวลำดับพลวัตที่ความจุไม่เป็นค่าคงที่ (หัวข้อถัด ๆ ไป) จะใช้หน่วยความจำเพียง Θ ( n + m ) {\displaystyle \Theta (n+m)} เท่านั้น

การขยายความจุเป็นค่าคงที่

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

ตารางแสดงจำนวนคำสั่งในการขยายความจุเมื่อความจุเพิ่มทีละ c

ครั้งที่ของการขยายความจุ	1 {\displaystyle 1}	2 {\displaystyle 2}	3 {\displaystyle 3}	...	k {\displaystyle k}	สรุป
ขนาดของแถวลำดับพลวัตในรอบนั้น ๆ	c {\displaystyle c}	2 × c {\displaystyle 2\times c}	3 × c {\displaystyle 3\times c}	...	k × c {\displaystyle k\times c}	ขนาดสุดท้าย	k × c {\displaystyle k\times c}
จำนวนคำสั่งในการคัดลอกข้อมูลในรอบนั้น ๆ	c {\displaystyle c}	2 × c {\displaystyle 2\times c}	3 × c {\displaystyle 3\times c}	...	k × c {\displaystyle k\times c}	รวมจำนวนคำสั่ง	( 1 + 2 + 3 + . . . + k ) × c {\displaystyle (1+2+3+...+k)\times c}

จากตาราง เมื่อมีการใส่ข้อมูลเข้ามาในแถวลำดับพลวัตเป็นจำนวน n = k × c {\displaystyle n=k\times c} ตัว จะมีการทำงานจากการจองหน่วยความจำและคัดลอกข้อมูลถึง ( 1 + 2 + . . . + k ) × c = Θ ( k 2 ) {\displaystyle (1+2+...+k)\times c=\Theta (k^{2})} ครั้ง เนื่องจาก k ∝ n {\displaystyle k\propto n} จะได้ว่าการใส่ข้อมูลเข้าไป n {\displaystyle n} ตัวใช้เวลาถึง Θ ( n 2 ) {\displaystyle \Theta (n^{2})} ถึงแม้วิธีนี้จะเสียเวลามาก แต่พื้นที่ที่สูญเสียไปก็คือส่วนที่ยังไม่ได้ใช้ซึ่งเป็นเพียงค่าคงที่เท่านั้น อย่างไรก็ตาม ในทางปฏิบัติมักจะคำนึงถึงความรวดเร็วของการทำงานมากกว่าพื้นที่ที่สูญเสียไป

การขยายความจุเป็นอัตราเรขาคณิตและการถัวเฉลี่ย

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

function insertEnd (dynarray a, element e)    if (a.size = a.capacity)        // resize a to c times of its current capacity:        a.capacity ← a.capacity * c        //  (copy the contents to the new memory location here)     a[a.size] ← e    a.size ← a.size + 1

เมื่อมีการใส่ข้อมูลตัวที่ n {\displaystyle n} เข้ามาและเกิดการขยายเกิดขึ้น จะมีการจองหน่วยความจำและคัดลอกข้อมูลซึ่งใช้เวลา Θ ( n ) {\displaystyle \Theta (n)} ความจุจะเพิ่มขึ้น c เท่า นั่นหมายความว่าเมื่อพิจารณาถึงจำนวนคำสั่งที่ใช้รวมทั้งหมด ความถี่ในการขยายขนาดในแต่ละครั้งจะห่างขึ้นเรื่อย ๆ เป็นอัตราเรขาคณิต ทำให้เมื่อวิเคราะห์แบบถัวเฉลี่ย การเพิ่มข้อมูลที่บางครั้ง Θ ( 1 ) {\displaystyle \Theta (1)} บางครั้ง Θ ( n ) {\displaystyle \Theta (n)} จะสามารถถัวเฉลี่ยให้ทุก ๆ การดำเนินการกลายเป็น Θ ( 1 ) {\displaystyle \Theta (1)} ได้ ตารางข้างล่างนี้แสดงถึงการขยายความจุที่ความจุเพิ่มเป็นอัตราเรขาคณิต

ตารางแสดงจำนวนคำสั่งในการขยายขนาดเมื่อความจุเพิ่มทีละ c เท่า

ครั้งที่ของการขยายขนาด	1 {\displaystyle 1}	2 {\displaystyle 2}	3 {\displaystyle 3}	...	k {\displaystyle k}	สรุป
ขนาดของแถวลำดับพลวัตในรอบนั้น ๆ	1 {\displaystyle 1}	c {\displaystyle c}	c 2 {\displaystyle c^{2}}	...	c k − 1 {\displaystyle c^{k-1}}	ขนาดสุดท้าย	c k − 1 {\displaystyle c^{k-1}}
จำนวนคำสั่งในการคัดลอกข้อมูลในรอบนั้น ๆ	1 {\displaystyle 1}	c {\displaystyle c}	c 2 {\displaystyle c^{2}}	...	c k − 1 {\displaystyle c^{k-1}}	รวมจำนวนคำสั่ง	1 + c + c 2 + . . . + c k − 1 {\displaystyle 1+c+c^{2}+...+c^{k-1}}

สรุปได้ว่าเมื่อมีการใส่ข้อมูลเข้ามาในแถวลำดับพลวัตเป็นจำนวน n = c k − 1 {\displaystyle n=c^{k-1}} ตัว จะมีการทำงาน 1 + c + c 2 + . . . + c k − 1 = Θ ( c k ) {\displaystyle 1+c+c^{2}+...+c^{k-1}=\Theta (c^{k})} ครั้ง เนื่องจาก k ∝ log c ⁡ n {\displaystyle k\propto \log _{c}n} จะได้ว่าการใส่ข้อมูลเข้าไป n {\displaystyle n} ตัวใช้เวลา Θ ( c log c ⁡ n ) = Θ ( n ) {\displaystyle \Theta (c^{\log _{c}n})=\Theta (n)} ดังนั้นจึงอาจถัวเฉลี่ยให้การดำเนินการเพิ่มข้อมูลครั้งหนึ่งใช้เวลา Θ ( 1 ) {\displaystyle \Theta (1)} ได้ ข้อเสียของแถวลำดับพลวัตที่ขยายความจุเป็นอัตราเรขาคณิตคือพื้นที่ที่เสียไปโดยไม่จำเป็นอาจมีมากถึงเชิงเส้น O ( n ) {\displaystyle O(n)} [1]

ค่า c นั้นสามารถเลือกใช้เป็นจำนวนใด ๆ ก็ได้ที่มากกว่า 1 เพื่อให้เห็นภาพได้ชัด หนังสือส่วนใหญ่ใช้ค่า c = 2 [3][4] แต่เพื่อให้พื้นที่ที่เสียไปโดยไม่จำเป็นไม่มากนัก ในทางปฏิบัติมักจะใช้ค่า c ที่น้อยกว่านั้น เช่น ArrayList ของภาษาจาวาใช้ค่า c = 3/2 [2] list ของภาษาไพธอน (ซึ่งเขียนด้วยภาษา C) ใช้ค่า c = 9/8[5]

แถวลำดับพลวัตเป็นตัวอย่างที่นิยมใช้ในการสอนเรื่องการวิเคราะห์แบบถัวเฉลี่ย[3][4]