Фарқи байни рӯйхати пайваст ва массив чист?

Масив сақтайды элементтерді жаға-жай орналасқан жады ұяшықтарында, тез қол жеткізу үшін индекс бойынша (O(1)). Өлшемі құрылғанда тұрақты.

Байланысқан тізім элементтерді сақтау үшін пайдаланады, әрқайсысы деректер мен келесі ұяшыққа сілтемеден тұрады. Индекс бойынша қол жеткізу үшін өтуді қажет етеді (O(n)). Өлшемі динамикалық.

Негізгі айырмашылықтар:

Ерекшелік	Масив	Байланысқан тізім
Орналасуы	Жақын орналасқан жады ұяшықтары	Сілтемелері бар ұяшықтар
Индекс бойынша қол жеткізу	Жылдам (O(1))	Баяу (O(n))
Қосу/жою	Баяу (O(n))	Жылдам (O(1)) бастапқыда/аяғында
Өлшемі	Тұрақты	Динамикалық

Массивке элемент қосу мысалы, жаңа массив құрып, элементтерді көшіруді талап етеді:

// Элемент қосу массивке
int[] бастапқыМассив = {1, 2, 3};
int жаңаМән = 4;
int[] жаңаМассив = new int[бастапқыМассив.length + 1];
System.arraycopy(бастапқыМассив, 0, жаңаМассив, 0, бастапқыМассив.length);
жаңаМассив[бастапқыМассив.length] = жаңаМән;

Байланысқан тізімге элемент қосу мысалы (соңына):

// Байланысқан тізімге элемент қосу
class Түйін {
    int деректер;
    Түйін келесі;
    Түйін(int d) { деректер = d; келесі = null; }
}
// ...
Түйін бас = new Түйін(1);
Түйін екінші = new Түйін(2);
бас.келесі = екінші;
Түйін соң = екінші; // екінші соңғы элемент деп есептейміз
Түйін жаңаТүйін = new Түйін(3);
соң.келесі = жаңаТүйін;
соң = жаңаТүйін; // соңын жаңарту