Масив и Свързан списък са двата начина за организиране на данните в паметта. Преди да разберете разликите между Масив и на Свързан списък , първо гледаме в масив и свързан списък .
сравнение с низове в java
Какво е масив?
Структура от данни, която съдържа елементи от един и същи тип. Структурата на данните е начин за организиране на данните; масивът е структура от данни, защото последователно организира данните. Масивът е голяма част от паметта, в която паметта е разделена на малки-малки блокове и всеки блок може да съхранява някаква стойност.
Да предположим, че сме създали масив, който се състои от 10 стойности, тогава всеки блок ще съхранява стойността от целочислен тип. Ако се опитаме да съхраним стойността в масив от различни типове, това не е правилен масив и ще изведе грешка по време на компилиране.
Декларация на масив
Масивът може да бъде деклариран като:
data_type name of the array[no of elements]
За да декларираме масив, първо трябва да посочим типа на масива и след това името на масива. Вътре в квадратните скоби трябва да посочим броя на елементите, които нашият масив трябва да съдържа.
Нека разберем чрез пример.
int a[5];
В горния случай сме декларирали масив от 5 елемента с ' а име на an цяло число тип данни.
Какво е свързан списък?
Свързаният списък е колекция от възли, които се съхраняват на случаен принцип. Всеки възел се състои от две полета, т.е. данни и връзка . Тук данните са стойността, съхранена в този конкретен възел, а връзката е указателят, който съдържа адреса на следващия възел.
python __име__
Разлики между масив и свързан списък
Не можем да кажем коя структура от данни е по-добра, т.е. масив или свързан списък . Може да има възможност една структура от данни да е по-добра за един вид изискване, докато другата структура от данни е по-добра за друг вид изискване. Има различни фактори, като например какви са често извършваните операции върху структурата на данните или размера на данните, както и други фактори, на базата на които се избира структурата на данните. Сега ще видим някои разлики между масива и свързания списък въз основа на някои параметри.
1. Цена за достъп до елемент
В случай на масив, независимо от размера на масива, масивът отнема постоянно време за достъп до елемент. В масива елементите се съхраняват по непрекъснат начин, така че ако знаем основния адрес на елемента, можем лесно да получим адреса на всеки елемент в масива. Трябва да извършим просто изчисление, за да получим адреса на всеки елемент в масива. И така, достъпът до елемента в масив е О(1) по отношение на времевата сложност.
В свързания списък елементите не се съхраняват по непрекъснат начин. Състои се от множество блокове и всеки блок е представен като възел. Всеки възел има две полета, т.е. едното е за полето с данни, а другото съхранява адреса на следващия възел. За да намерим възел в свързания списък, първо трябва да определим първия възел, известен като главен възел. Ако трябва да намерим втория възел в списъка, тогава трябва да преминем от първия възел, а в най-лошия случай, за да намерим последния възел, ще преминем през всички възли. Средният случай за достъп до елемента е O(n).
Ние заключаваме, че цената за достъп до елемент в масива е по-малка от свързания списък. Следователно, ако имаме някакво изискване за достъп до елементите, тогава масивът е по-добър избор.
2. Разходи за вмъкване на елемент
При вмъкването може да има три сценария:
В случай на свързан списък, за да вмъкнем елемент в началото на свързания списък, ще създадем нов възел и адресът на първия възел се добавя към новия възел. По този начин новият възел става първият възел. Така че времевата сложност не е пропорционална на размера на списъка. Времевата сложност ще бъде постоянна, т.е. O(1).
Ако масивът не е пълен, тогава можем директно да добавим новия елемент чрез индекса. В този случай времевата сложност ще бъде постоянна, т.е. O(1). Ако масивът е пълен, първо трябва да копираме масива в друг масив и да добавим нов елемент. В този случай времевата сложност ще бъде O(n).
За да вмъкнем елемент в края на свързания списък, трябва да обходим целия списък. Ако свързаният списък се състои от n елемента, тогава времевата сложност ще бъде O(n).
Да предположим, че искаме да вмъкнем елемента в ithпозиция на масива; трябва да преместим n/2 елемента надясно. Следователно времевата сложност е пропорционална на броя на елементите. Времевата сложност би била O(n) за средния случай.
fmoviez
В случай на свързан списък, трябва да преминем към тази позиция, където трябва да вмъкнем новия елемент. Въпреки това, ние не трябва да извършваме какъвто и да е вид преместване, но трябва да преминем към позиция n/2. Отнетото време е пропорционално на n броя елементи, а времевата сложност за средния случай би била O(n).
Полученият свързан списък е:
Внедряването на масив е лесно в сравнение със свързания списък. Докато създавате програма с помощта на свързан списък, програмата е по-податлива на грешки като грешка при сегментиране или изтичане на памет. Така че трябва да се внимава много, докато се създава програма в свързания списък.
Свързаният списък е динамичен по размер, докато масивът е статичен. Тук статичността не означава, че не можем да решим размера по време на изпълнение, но не можем да го променим, след като размерът е определен.
3. Изисквания към паметта
Тъй като елементите в масива се съхраняват в един непрекъснат блок от паметта, масивът е с фиксиран размер. Да предположим, че имаме масив с размер 7 и масивът се състои от 4 елемента, тогава останалото пространство е неизползвано. Паметта, заета от 7-те елемента:
Пространство в паметта = 7*4 = 28 байта
Където 7 е броят на елементите в масива, а 4 е броят на байтовете от целочислен тип.
В случай на свързан списък няма неизползвана памет, но допълнителната памет е заета от променливите на указателя. Ако данните са от целочислен тип, тогава общата памет, заета от един възел, е 8 байта, т.е. 4 байта за данни и 4 байта за променлива указател. Ако свързаният списък се състои от 4 елемента, тогава пространството в паметта, заемано от свързания списък, ще бъде:
уебдрайвер
Пространство в паметта = 8*4 = 32 байта
Свързаният списък би бил по-добър избор, ако частта с данни е с по-голям размер. Да предположим, че данните са от 16 байта. Пространството в паметта, заето от масива, ще бъде 16*7=112 байта, докато свързаният списък заема 20*4=80, тук сме посочили 20 байта като 16 байта за размера на данните плюс 4 байта за променливата на указателя. Ако изберем по-големия размер на данните, тогава свързаният списък ще консумира по-малко памет; в противен случай зависи от факторите, които приемаме, за да определим размера.
Нека да разгледаме разликите между масива и свързания списък в таблична форма.
| Масив | Свързан списък |
|---|---|
| Масивът е колекция от елементи от подобен тип данни. | Свързаният списък е колекция от обекти, известни като възел, където възелът се състои от две части, т.е. данни и адрес. |
| Елементите на масива се съхраняват в непрекъснато място в паметта. | Елементите на свързания списък могат да се съхраняват навсякъде в паметта или да се съхраняват произволно. |
| Масивът работи със статична памет. Тук статичната памет означава, че размерът на паметта е фиксиран и не може да се променя по време на изпълнение. | Свързаният списък работи с динамична памет. Тук динамичната памет означава, че размерът на паметта може да се променя по време на изпълнение според нашите изисквания. |
| Елементите на масива са независими един от друг. | Елементите на свързания списък са зависими един от друг. Тъй като всеки възел съдържа адреса на следващия възел, така че за да осъществим достъп до следващия възел, трябва да осъществим достъп до неговия предишен възел. |
| Масивът отнема повече време при извършване на всяка операция като вмъкване, изтриване и т.н. | Свързаният списък отнема по-малко време при извършване на всяка операция като вмъкване, изтриване и т.н. |
| Достъпът до всеки елемент в масив е по-бърз, тъй като елементът в масив може да бъде директно достъпен чрез индекса. | Достъпът до елемент в свързан списък е по-бавен, тъй като той започва преминаването от първия елемент на свързания списък. |
| В случай на масив паметта се разпределя по време на компилация. | В случай на свързан списък паметта се разпределя по време на изпълнение. |
| Използването на паметта е неефективно в масива. Например, ако размерът на масива е 6 и масивът се състои само от 3 елемента, тогава останалото пространство ще бъде неизползвано. | Използването на паметта е ефективно в случай на свързан списък, тъй като паметта може да бъде разпределена или освободена по време на изпълнение според нашите изисквания. |