ਦੋਵੇਂ ਕ੍ਰਮ ਸਟੋਰ ਕਰਦੇ ਹਨ, ਪਰ ਉਨ੍ਹਾਂ ਦੇ ਉਲਟ ਲਾਗਤ ਪ੍ਰੋਫਾਈਲ ਹਨ। ਇੱਕ array ਲਗਾਤਾਰ ਮੈਮੋਰੀ ਹੈ ਜਿਸ ਵਿੱਚ O(1) ਇੰਡੈਕਸਿੰਗ ਹੈ; ਇੱਕ linked list ਪੁਆਇੰਟਰਾਂ ਦੁਆਰਾ ਜੁੜੇ ਹੋਏ ਖਿੰਡੇ ਹੋਏ ਨੋਡਸ ਹਨ, ਜਿਨ੍ਹਾਂ ਵਿੱਚ ਸਿਰਿਆਂ ਵਿਖੇ O(1) ਇਨਸਰਟ/ਡਿਲੀਟ ਹੈ ਪਰ ਕੋਈ ਇੰਡੈਕਸਿੰਗ ਨਹੀਂ।
ਦੋਵੇਂ ਕ੍ਰਮ ਸਟੋਰ ਕਰਦੇ ਹਨ, ਪਰ ਉਨ੍ਹਾਂ ਦੇ ਉਲਟ ਲਾਗਤ ਪ੍ਰੋਫਾਈਲ ਹਨ। ਇੱਕ array ਲਗਾਤਾਰ ਮੈਮੋਰੀ ਹੈ ਜਿਸ ਵਿੱਚ O(1) ਇੰਡੈਕਸਿੰਗ ਹੈ; ਇੱਕ linked list ਪੁਆਇੰਟਰਾਂ ਦੁਆਰਾ ਜੁੜੇ ਹੋਏ ਖਿੰਡੇ ਹੋਏ ਨੋਡਸ ਹਨ, ਜਿਨ੍ਹਾਂ ਵਿੱਚ ਸਿਰਿਆਂ ਵਿਖੇ O(1) ਇਨਸਰਟ/ਡਿਲੀਟ ਹੈ ਪਰ ਕੋਈ ਇੰਡੈਕਸਿੰਗ ਨਹੀਂ।
| ਓਪਰੇਸ਼ਨ | Array (dynamic) | Linked list |
|---|
| Index ਦੁਆਰਾ ਐਕਸੈਸ | O(1) | O(n) |
| ਖੋਜ | O(n) | O(n) |
| Head ਵਿੱਚ ਇਨਸਰਟ/ਡਿਲੀਟ | O(n) | O(1) |
| Tail ਵਿੱਚ ਇਨਸਰਟ/ਡਿਲੀਟ | O(1) amortized | O(1) tail ptr ਦੇ ਨਾਲ |
| ਮੱਧ ਵਿੱਚ ਇਨਸਰਟ/ਡਿਲੀਟ | O(n) | O(n) ਖੋਜ + O(1) splice |
| ਮੈਮੋਰੀ ਓਵਰਹੈੱਡ | ਘੱਟ | ਉੱਚ (ਪ੍ਰਤੀ ਨੋਡ ਪੁਆਇੰਟਰ) |
| Cache ਸਥਿਤੀ | ਸ਼ਾਨਦਾਰ | ਕਮਜ਼ੋਰ |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
ਵਿਅਰਥ ਅਮਲ ਵਿਚ arrays ਆਮ ਤੌਰ 'ਤੇ ਜਿੱਤਦੇ ਹਨ ਕਿਉਂਕਿ cache ਸਥਿਤੀ ਆਮ ਆਕਾਰਾਂ ਲਈ Big-O ਅੰਤਰ ਨੂੰ ਆਪਸ ਵਿਚ ਪਾਲ ਦਿੰਦਾ ਹੈ।
ਦੋਵਾਂ ਨੂੰ ਜਾਣਨਾ ਤੁਹਾਨੂੰ ਅਜ਼ਮਾਈਸ਼ਾਂ ਵਿੱਚ ਅਪਣੀ ਪਸੰਦ ਨੂੰ ਜਾਇਜ਼ ਠਹਿਰਾਉਣ ਦੀ ਪ੍ਰਤਿ ਕਰਦਾ ਹੈ ਨੱਕੇਪਾ ਡਿਫੋਲਟ ਦੀ ਬਜਾਏ — ਅਤੇ ਸਮਝਾ ਸਕਦੇ ਹੋ ਕਿਉਂ "O(1) ਇਨਸਰਟ" ਘੱਟ ਕਰਕੇ ਇੱਕ ਨਿਰੰਤਰ array ਨੂੰ ਹਰਾਉਂਦਾ ਹੈ।