(۰۴ بهمن ۱۳۹۳ ۰۸:۱۹ ب.ظ)shamim_70 نوشته شده توسط:  سلام
در لیست پیوندی دو طرفه اگ فقط اشاره گر اول لیست رو داشته باشیم درج و حذف در ابتدا یا انتهای ی لیست میشه از مرتبهO)1(?جستجو عنصر چی؟

(۰۴ بهمن ۱۳۹۳ ۱۰:۲۹ ب.ظ)moloodi نوشته شده توسط:  این یه لیست پیوندی دوطرفه



با توجه به شکل درج در ابتدا (O(1

درج در انتها بدون داشتن اشاره گر به انتها از مرتبه (O(n

جستجو از مرتبه (O(n مرتب بودن یا نبودن هم روش تاثیری نداره.

(۰۵ بهمن ۱۳۹۳ ۰۷:۲۹ ق.ظ)shamim_70 نوشته شده توسط:  حذف از انتها چون اشاره گره به عنصر قبل رو داریم ک نیازی نیس ی پیمایش از اول انجام بدیم ک بشه( O(n ؟؟

(۰۵ بهمن ۱۳۹۳ ۰۱:۴۲ ب.ظ)ziba.O نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۷:۲۹ ق.ظ)shamim_70 نوشته شده توسط:  حذف از انتها چون اشاره گره به عنصر قبل رو داریم ک نیازی نیس ی پیمایش از اول انجام بدیم ک بشه( O(n ؟؟

نگفته اشاره گر به عنصر آخر داریم فقط اشاره گر به عنصر اولو داریم با توجه به سوال.
درج در انتها بدون داشتن اشاره گر به انتها از مرتبه (O(n درصورت داشتن اشاره گر به انتها از مرتبه ی (O(1 هست.
حذف از ابتدا از مرتبه ی (O(1 و حذف از انتها اگه اشاره گر به انتها رو داشته باشیم یا نداشته باشیم از مرتبه ی (O(n هست چون آدرس عنصر ماقبل رو نداریمو ماباید اشاره گر سمت راست عنصر ماقبل آخرو تهی کنیم که این نیاز به پیمایش لیست داره.

(۰۵ بهمن ۱۳۹۳ ۰۱:۴۰ ب.ظ)moloodi نوشته شده توسط:  یکی از تفاوت های مهم لیست پیوندی دوطرفه با لیست پیوندی ساده مساله حذف عناصر هست.
حذف به این صورت بررسی میشه که برای ما قبلا عنصر مورد نظر پیدا شده (مثلا توسط قسمت دیگه ای از برنامه) و فقط وظیفه حذف و بروزرسانی لیست به عهده ماست.
در لیست پیوندی ساده به دلیل در دسترس نبودن عنصر قبلی ، لیست باید از ابتدا پیمایش شود، ولی اگر لیست دو طرفه باشد این پیمایش نیاز نیست و عملیات از مرتبه (O(1 خواهد بود.

(۰۵ بهمن ۱۳۹۳ ۰۲:۰۷ ب.ظ)shamim_70 نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۱:۴۲ ب.ظ)ziba.O نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۷:۲۹ ق.ظ)shamim_70 نوشته شده توسط:  حذف از انتها چون اشاره گره به عنصر قبل رو داریم ک نیازی نیس ی پیمایش از اول انجام بدیم ک بشه( O(n ؟؟

نگفته اشاره گر به عنصر آخر داریم فقط اشاره گر به عنصر اولو داریم با توجه به سوال.
درج در انتها بدون داشتن اشاره گر به انتها از مرتبه (O(n درصورت داشتن اشاره گر به انتها از مرتبه ی (O(1 هست.
حذف از ابتدا از مرتبه ی (O(1 و حذف از انتها اگه اشاره گر به انتها رو داشته باشیم یا نداشته باشیم از مرتبه ی (O(n هست چون آدرس عنصر ماقبل رو نداریمو ماباید اشاره گر سمت راست عنصر ماقبل آخرو تهی کنیم که این نیاز به پیمایش لیست داره.

خب خود عنصر اخر اشاره گری ب عنصر کناریش داره دیگه!(مث اینک لیست دو طرفه هستااا)

---

(۰۵ بهمن ۱۳۹۳ ۰۱:۴۰ ب.ظ)moloodi نوشته شده توسط:  یکی از تفاوت های مهم لیست پیوندی دوطرفه با لیست پیوندی ساده مساله حذف عناصر هست.
حذف به این صورت بررسی میشه که برای ما قبلا عنصر مورد نظر پیدا شده (مثلا توسط قسمت دیگه ای از برنامه) و فقط وظیفه حذف و بروزرسانی لیست به عهده ماست.
در لیست پیوندی ساده به دلیل در دسترس نبودن عنصر قبلی ، لیست باید از ابتدا پیمایش شود، ولی اگر لیست دو طرفه باشد این پیمایش نیاز نیست و عملیات از مرتبه (O(1 خواهد بود.

منم همین نکته ای ک شما گفتیدو یجا دیدم ک با داشتن ادرس عنصری ک می خوایم حذف کنیم دیگ نیازی ب پیمابش برای رسیدن ب عنصر ماقبل نیست واسه همین حذف از مرتبه ۱هست
حالا شما میگید براساس این نکته این درست هس که بگیم حذف از انتها (انتهای لیست ادرسش مشخصه)از مرتبه۱هست؟؟؟
درج در انتها با دونستن همین فرض چجوریه؟

(۰۵ بهمن ۱۳۹۳ ۰۲:۵۹ ب.ظ)ziba.O نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۲:۰۷ ب.ظ)shamim_70 نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۱:۴۲ ب.ظ)ziba.O نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۷:۲۹ ق.ظ)shamim_70 نوشته شده توسط:  حذف از انتها چون اشاره گره به عنصر قبل رو داریم ک نیازی نیس ی پیمایش از اول انجام بدیم ک بشه( O(n ؟؟

نگفته اشاره گر به عنصر آخر داریم فقط اشاره گر به عنصر اولو داریم با توجه به سوال.
درج در انتها بدون داشتن اشاره گر به انتها از مرتبه (O(n درصورت داشتن اشاره گر به انتها از مرتبه ی (O(1 هست.
حذف از ابتدا از مرتبه ی (O(1 و حذف از انتها اگه اشاره گر به انتها رو داشته باشیم یا نداشته باشیم از مرتبه ی (O(n هست چون آدرس عنصر ماقبل رو نداریمو ماباید اشاره گر سمت راست عنصر ماقبل آخرو تهی کنیم که این نیاز به پیمایش لیست داره.

خب خود عنصر اخر اشاره گری ب عنصر کناریش داره دیگه!(مث اینک لیست دو طرفه هستااا)

---

(۰۵ بهمن ۱۳۹۳ ۰۱:۴۰ ب.ظ)moloodi نوشته شده توسط:  یکی از تفاوت های مهم لیست پیوندی دوطرفه با لیست پیوندی ساده مساله حذف عناصر هست.
حذف به این صورت بررسی میشه که برای ما قبلا عنصر مورد نظر پیدا شده (مثلا توسط قسمت دیگه ای از برنامه) و فقط وظیفه حذف و بروزرسانی لیست به عهده ماست.
در لیست پیوندی ساده به دلیل در دسترس نبودن عنصر قبلی ، لیست باید از ابتدا پیمایش شود، ولی اگر لیست دو طرفه باشد این پیمایش نیاز نیست و عملیات از مرتبه (O(1 خواهد بود.

منم همین نکته ای ک شما گفتیدو یجا دیدم ک با داشتن ادرس عنصری ک می خوایم حذف کنیم دیگ نیازی ب پیمابش برای رسیدن ب عنصر ماقبل نیست واسه همین حذف از مرتبه ۱هست
حالا شما میگید براساس این نکته این درست هس که بگیم حذف از انتها (انتهای لیست ادرسش مشخصه)از مرتبه۱هست؟؟؟
درج در انتها با دونستن همین فرض چجوریه؟

آره اون یادم رفته بود. یعنی میگی فقط اشاره گر سمت راست عنصر آخرو تهی کنیمو با عنصر ماقبلش کاری نداشته باشیم؟ یا با آدرس بریم اشاره گر عنصرماقبلو تهی کنیم؟

(۰۵ بهمن ۱۳۹۳ ۰۸:۵۱ ب.ظ)shamim_70 نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۲:۵۹ ب.ظ)ziba.O نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۲:۰۷ ب.ظ)shamim_70 نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۱:۴۲ ب.ظ)ziba.O نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۷:۲۹ ق.ظ)shamim_70 نوشته شده توسط:  حذف از انتها چون اشاره گره به عنصر قبل رو داریم ک نیازی نیس ی پیمایش از اول انجام بدیم ک بشه( O(n ؟؟

نگفته اشاره گر به عنصر آخر داریم فقط اشاره گر به عنصر اولو داریم با توجه به سوال.
درج در انتها بدون داشتن اشاره گر به انتها از مرتبه (O(n درصورت داشتن اشاره گر به انتها از مرتبه ی (O(1 هست.
حذف از ابتدا از مرتبه ی (O(1 و حذف از انتها اگه اشاره گر به انتها رو داشته باشیم یا نداشته باشیم از مرتبه ی (O(n هست چون آدرس عنصر ماقبل رو نداریمو ماباید اشاره گر سمت راست عنصر ماقبل آخرو تهی کنیم که این نیاز به پیمایش لیست داره.

خب خود عنصر اخر اشاره گری ب عنصر کناریش داره دیگه!(مث اینک لیست دو طرفه هستااا)

---

(۰۵ بهمن ۱۳۹۳ ۰۱:۴۰ ب.ظ)moloodi نوشته شده توسط:  یکی از تفاوت های مهم لیست پیوندی دوطرفه با لیست پیوندی ساده مساله حذف عناصر هست.
حذف به این صورت بررسی میشه که برای ما قبلا عنصر مورد نظر پیدا شده (مثلا توسط قسمت دیگه ای از برنامه) و فقط وظیفه حذف و بروزرسانی لیست به عهده ماست.
در لیست پیوندی ساده به دلیل در دسترس نبودن عنصر قبلی ، لیست باید از ابتدا پیمایش شود، ولی اگر لیست دو طرفه باشد این پیمایش نیاز نیست و عملیات از مرتبه (O(1 خواهد بود.

منم همین نکته ای ک شما گفتیدو یجا دیدم ک با داشتن ادرس عنصری ک می خوایم حذف کنیم دیگ نیازی ب پیمابش برای رسیدن ب عنصر ماقبل نیست واسه همین حذف از مرتبه ۱هست
حالا شما میگید براساس این نکته این درست هس که بگیم حذف از انتها (انتهای لیست ادرسش مشخصه)از مرتبه۱هست؟؟؟
درج در انتها با دونستن همین فرض چجوریه؟

آره اون یادم رفته بود. یعنی میگی فقط اشاره گر سمت راست عنصر آخرو تهی کنیمو با عنصر ماقبلش کاری نداشته باشیم؟ یا با آدرس بریم اشاره گر عنصرماقبلو تهی کنیم؟

با اشاره گر سمت چپ عنصر اخر میتونیم بریم ب ماقابلش بعد اشاره سمت راست عنصر ماقبلو بقول شما تهی کنیم!ولی نمیدونم این چقد درسته!!!!اصلا میشه همچین کاری کرد یا نه؟

(۰۵ بهمن ۱۳۹۳ ۰۸:۵۱ ب.ظ)shamim_70 نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۲:۵۹ ب.ظ)ziba.O نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۲:۰۷ ب.ظ)shamim_70 نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۱:۴۲ ب.ظ)ziba.O نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۷:۲۹ ق.ظ)shamim_70 نوشته شده توسط:  حذف از انتها چون اشاره گره به عنصر قبل رو داریم ک نیازی نیس ی پیمایش از اول انجام بدیم ک بشه( O(n ؟؟

نگفته اشاره گر به عنصر آخر داریم فقط اشاره گر به عنصر اولو داریم با توجه به سوال.
درج در انتها بدون داشتن اشاره گر به انتها از مرتبه (O(n درصورت داشتن اشاره گر به انتها از مرتبه ی (O(1 هست.
حذف از ابتدا از مرتبه ی (O(1 و حذف از انتها اگه اشاره گر به انتها رو داشته باشیم یا نداشته باشیم از مرتبه ی (O(n هست چون آدرس عنصر ماقبل رو نداریمو ماباید اشاره گر سمت راست عنصر ماقبل آخرو تهی کنیم که این نیاز به پیمایش لیست داره.

خب خود عنصر اخر اشاره گری ب عنصر کناریش داره دیگه!(مث اینک لیست دو طرفه هستااا)

---

(۰۵ بهمن ۱۳۹۳ ۰۱:۴۰ ب.ظ)moloodi نوشته شده توسط:  یکی از تفاوت های مهم لیست پیوندی دوطرفه با لیست پیوندی ساده مساله حذف عناصر هست.
حذف به این صورت بررسی میشه که برای ما قبلا عنصر مورد نظر پیدا شده (مثلا توسط قسمت دیگه ای از برنامه) و فقط وظیفه حذف و بروزرسانی لیست به عهده ماست.
در لیست پیوندی ساده به دلیل در دسترس نبودن عنصر قبلی ، لیست باید از ابتدا پیمایش شود، ولی اگر لیست دو طرفه باشد این پیمایش نیاز نیست و عملیات از مرتبه (O(1 خواهد بود.

منم همین نکته ای ک شما گفتیدو یجا دیدم ک با داشتن ادرس عنصری ک می خوایم حذف کنیم دیگ نیازی ب پیمابش برای رسیدن ب عنصر ماقبل نیست واسه همین حذف از مرتبه ۱هست
حالا شما میگید براساس این نکته این درست هس که بگیم حذف از انتها (انتهای لیست ادرسش مشخصه)از مرتبه۱هست؟؟؟
درج در انتها با دونستن همین فرض چجوریه؟

آره اون یادم رفته بود. یعنی میگی فقط اشاره گر سمت راست عنصر آخرو تهی کنیمو با عنصر ماقبلش کاری نداشته باشیم؟ یا با آدرس بریم اشاره گر عنصرماقبلو تهی کنیم؟

با اشاره گر سمت چپ عنصر اخر میتونیم بریم ب ماقابلش بعد اشاره سمت راست عنصر ماقبلو بقول شما تهی کنیم!ولی نمیدونم این چقد درسته!!!!اصلا میشه همچین کاری کرد یا نه؟

(۰۶ بهمن ۱۳۹۳ ۰۸:۵۲ ق.ظ)tm.viper نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۸:۵۱ ب.ظ)shamim_70 نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۲:۵۹ ب.ظ)ziba.O نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۲:۰۷ ب.ظ)shamim_70 نوشته شده توسط:  

(05 بهمن ۱۳۹۳ ۰۱:۴۲ ب.ظ)ziba.O نوشته شده توسط:  نگفته اشاره گر به عنصر آخر داریم فقط اشاره گر به عنصر اولو داریم با توجه به سوال.
درج در انتها بدون داشتن اشاره گر به انتها از مرتبه (O(n درصورت داشتن اشاره گر به انتها از مرتبه ی (O(1 هست.
حذف از ابتدا از مرتبه ی (O(1 و حذف از انتها اگه اشاره گر به انتها رو داشته باشیم یا نداشته باشیم از مرتبه ی (O(n هست چون آدرس عنصر ماقبل رو نداریمو ماباید اشاره گر سمت راست عنصر ماقبل آخرو تهی کنیم که این نیاز به پیمایش لیست داره.

خب خود عنصر اخر اشاره گری ب عنصر کناریش داره دیگه!(مث اینک لیست دو طرفه هستااا)

---

(۰۵ بهمن ۱۳۹۳ ۰۱:۴۰ ب.ظ)moloodi نوشته شده توسط:  یکی از تفاوت های مهم لیست پیوندی دوطرفه با لیست پیوندی ساده مساله حذف عناصر هست.
حذف به این صورت بررسی میشه که برای ما قبلا عنصر مورد نظر پیدا شده (مثلا توسط قسمت دیگه ای از برنامه) و فقط وظیفه حذف و بروزرسانی لیست به عهده ماست.
در لیست پیوندی ساده به دلیل در دسترس نبودن عنصر قبلی ، لیست باید از ابتدا پیمایش شود، ولی اگر لیست دو طرفه باشد این پیمایش نیاز نیست و عملیات از مرتبه (O(1 خواهد بود.

منم همین نکته ای ک شما گفتیدو یجا دیدم ک با داشتن ادرس عنصری ک می خوایم حذف کنیم دیگ نیازی ب پیمابش برای رسیدن ب عنصر ماقبل نیست واسه همین حذف از مرتبه ۱هست
حالا شما میگید براساس این نکته این درست هس که بگیم حذف از انتها (انتهای لیست ادرسش مشخصه)از مرتبه۱هست؟؟؟
درج در انتها با دونستن همین فرض چجوریه؟

آره اون یادم رفته بود. یعنی میگی فقط اشاره گر سمت راست عنصر آخرو تهی کنیمو با عنصر ماقبلش کاری نداشته باشیم؟ یا با آدرس بریم اشاره گر عنصرماقبلو تهی کنیم؟

با اشاره گر سمت چپ عنصر اخر میتونیم بریم ب ماقابلش بعد اشاره سمت راست عنصر ماقبلو بقول شما تهی کنیم!ولی نمیدونم این چقد درسته!!!!اصلا میشه همچین کاری کرد یا نه؟

دوطرفه با چرخشی فرق داره ها

(۰۶ بهمن ۱۳۹۳ ۱۲:۵۲ ب.ظ)tm.viper نوشته شده توسط:  من بد خوندم جواب شما رو
الان که فکر میکنم عنصر آخر درتبه n حذف میشه
اشاره گر به اول داربم و هیچ راهی نیست جز این که ابن اشاره گر رو ببریم جلو
اگه آرایه بود میگفتیم اندیس فلان
اما اینجا فقط یه اندیس هست که همون اشاره گره!
مثل به قلم که باید روی یه خط حرکت کنه

---

دوطرفه بودن فقط اجازه میده که قلم رو در دو جهت حرکت بدیم
حالا اگه اشاره گر به آخر هم بود میشد دوتا قلم داشت از اول به آخر و از آخر به اول که هر کدوم در دو جهت حرکت میکنن(دوتا اندیس)

(۰۶ بهمن ۱۳۹۳ ۰۱:۰۳ ب.ظ)ziba.O نوشته شده توسط:  

(06 بهمن ۱۳۹۳ ۱۲:۵۲ ب.ظ)tm.viper نوشته شده توسط:  من بد خوندم جواب شما رو

الان که فکر میکنم عنصر آخر درتبه n حذف میشه

اشاره گر به اول داربم و هیچ راهی نیست جز این که ابن اشاره گر رو ببریم جلو

اگه آرایه بود میگفتیم اندیس فلان

اما اینجا فقط یه اندیس هست که همون اشاره گره!

مثل به قلم که باید روی یه خط حرکت کنه

---

دوطرفه بودن فقط اجازه میده که قلم رو در دو جهت حرکت بدیم

حالا اگه اشاره گر به آخر هم بود میشد دوتا قلم داشت از اول به آخر و از آخر به اول که هر کدوم در دو جهت حرکت میکنن(دوتا اندیس)

خب حالا اگه اشاره گر به آخر داشته باشیم مرتبه ی زمانی حذف از آخر چی میشه؟