💻 آخرین فرصت یادگیری برنامه‌نویسی با آفر ویژه قبل از افزایش قیمت در ۱۵ آذر ماه (🎁 به همراه یک هدیه ارزشمند )
۰ ثانیه
۰ دقیقه
۰ ساعت
۵ امیر رحمانی
در LinkedList موقع حذف آیتمی از لیست، اون قسمت از حافظه از بین میره کلا؟
جامعه جاوا (وب و دسکتاپ) ایجاد شده در ۱۴ اردیبهشت ۱۴۰۱

سلام استاد وقت بخیر

چند تا سوال برام پیش اومد از ArrayList و LinkedList

استاد گفتید LinkedList میاد دیتا و آدرس دیتا بعدی رو تو حافظه ذخیره میکنه و وقتی ما عنصری رو حذف می‌کنیم linkedList به ایندکس یا آدرس دیتا بعدی اشاره می‌کنه و درواقع داده‌ها دیگه شیفت پیدا نمیکنن به اون ایندکس که حذف شده از حافظه برا همین سریع تره موقع اضافه کردن و ریموو کردن و یا تغییر دادن نسبت به ArrayList.

1-الان ما اگه یه LinkedList داشته باشیم یه عنصری رو حذف کنیم اون قسمت از حافظه که دیتاش حذف شده از بین میره دیگه و دیگه بهش دسترسی نداریم؟

2- LinkedList موقع ذخیره کردن هم دیتارو ذخیره میکنه هم ایندکس یا آدرس دیتا بعدی رو تو حافظه. پس نباید موقع add کردن کند‌تر باشه از ArrayList؟ چون ArrayList فقط دیتا رو ذخیره میکرد.

ممنون

سلام امیر جان،

جواب سوال اول بله.

در مورد سوال دوم منظور شما از ذخیره کردن چی هست؟

سپهر نامدار ۱۴ اردیبهشت ۱۴۰۱، ۰۷:۱۸

در مورد سوال دوم استاد منظورمون Add کردن است که دیتا روی حافظه قرار می‌گیره و ذخیره (store) میشه.

در مورد سوال اول پس یعنی مدیریت حافظه ام تو این حالت با خودمون باید باشه؟

*اصلاح شده*

امیر رحمانی ۱۴ اردیبهشت ۱۴۰۱، ۰۷:۴۷

خیر شما هیچ وقت در جاوا خودتون حافظه رو مدیریت نمیکنید و جاوا این کار رو برای شما به صورت دینامیک انجام میده. مثل زبان سی نیست که مجبور باشید خودتون دستی این کاررو بکنید.

در مورد سوال دوم فرض کنید یک لیست ۱۰۰۰ تایی داریم. اگر از آرای لیست استفاده کنید، برای اضافه کردن یک المان جاوا باید بیاد یکی یکی از ایندکس اول ۱۰۰۰ تا جلو بیاد تا به آخرین المان برسه و اون رو در حافظه جا بده. پس یعنی هر چی لیست بزرگتر باشه، پیدا کردن آخرین ایندکس هم طولانی تره. اما برای لینکدلیست اینجوری نیست، هر المانی که میخواین اضافه کنید به آخرین حافظه لیست اضافه میشه و هیچ ربطی به اندازه لیست نداره.

برعکس برای پیدا کردن یک المان ارای لیست بهتره چون از طریق ایندکس بلافاصله میشه المان مورد نظر رو پیدا کرد اما توی لینکد لیست باید جاوا یکی یکی بگرده تا به المان مورد نظر برسه.

سپهر نامدار ۱۴ اردیبهشت ۱۴۰۱، ۱۰:۳۰

آها الان متوجه شدم ممنون استاد، پس یک از دلایل اینکه لینکد لیست آدرس دیتا بعدی رو ذخیره میکنه برای همینه یعنی هربار آدرس آخرین حافظه لیست که نال هستش رو ذخیره میکنه، که بعدا ممکن ما بهش چیزی اضافه کنیم یا نکنیم.

این چیزی که داریم میگیم درسته استاد؟

امیر رحمانی ۱۴ اردیبهشت ۱۴۰۱، ۱۳:۱۱

سلام امیر جان

درمورد کلیت LinkedList بخام بگم ما دو تا Pointer نگه میداریم که یکی head هست که به اولین عنصر در لیست اشاره میکنه و یکی tail هست که به اخرین عضو در لیست اشاره میکند توی ساختمان داده به اینها sentinel یا نگهبان میگن

هر Node در لینکید لیست شامل دو قسمت هست یکی value و یکی هم next که ادرس خونه بعدی داخلش نوشته شده


اما جواب اخرین کامنتتون که پرسیدید درسته امیر جاان(البته اخرین Node ما در لینکید لیست value خودشو ذخیره کرده و همینطور داره اشاره میکنه به null چون بعدش هیچ Node دیگه ای قرار نگرفته ) طبق تصویر زیر ایتم اخری داره به نال اشاره میکنه


یه مورد برای مطالعه بیشتر(شاید براتون جالب باشه) :

خود لینکید لیست هم دو تا هست که یکی دابلی لینکید لیست هست و دیگری سینگل لینکید لیست هست

اگر انعطاف بیشتری میخاین در ازای حافظه بیشتر دادن : لینکید لیست دو طرفه مناسب هست یا همون دابلی لنکید لیست

اگر سادگی و انعطاف کمتر میخاین و حافظه کمتر لیست پیوندی تک طرفه یا سینگل لینکید لیست مناسب خواهد بود


اگر باز هم دوست دارید بیشتر در ساختمان داده عمیق شید میتونید کتاب goodritch data structure in java مطالعه کنین

4d65-Singly-Linked-List1.png

بهترین پاسخ
پوریا شفیعی ۱۵ اردیبهشت ۱۴۰۱، ۰۸:۲۱