اگه اشاره گر به اخرین عنصر رو داشته باشیم و لیست هم یک طرفه باشه و بخوایم عنصر اخر رو حذف کنیم مرتبش $O(n)$ میشه
اگه اشاره گر به اخرین عنصر رو داشته باشیم و لیست هم دو طرفه باشه و بخوایم عنصر اخر رو حذف کنیم مرتبش $O(1)$ میشه

این یه لیست پیوندی دوطرفه



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

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

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

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



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

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

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

منم با ایشون موافقم، حذف از انتها هم در هر صورت از مرتبه n هست؟

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

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

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

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

(۰۵ بهمن ۱۳۹۳ ۰۱:۴۲ ب.ظ)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 خواهد بود.

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

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

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

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

کجای توصیحات من لیست چرخشی رو توصیف کرد؟!!!
یکی نیسسس با اطمیناااان بگ حذف و درج در انتهای لیست دوطرفه از چ مرتبه ایه؟؟؟؟

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

---

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

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

---

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

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

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

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

---

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

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

سلام.اگه اشاره گر به اخرین عنصر رو داشته باشیم و لیست هم یک طرفه باشه و بخوایم عنصر اخر رو حذف کنیم مرتبش $O(n)$ میشه

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

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

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

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

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

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

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

---

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

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

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

اگر اشاره گر آخر رو داشته باشیم
مثل این میمونه تو آرایه به ما اندازه کل آرایه رو داده باشن
و با دونستن اون اندیس عنصر رو حذف میکنیم با مرتبه ۱

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

(06 بهمن ۱۳۹۳ ۰۱:۰۳ ب.ظ)ziba.O نوشته شده توسط:  خب حالا اگه اشاره گر به آخر داشته باشیم مرتبه ی زمانی حذف از آخر چی میشه؟

اگر اشاره گر آخر رو داشته باشیم
مثل این میمونه تو آرایه به ما اندازه کل آرایه رو داده باشن
و با دونستن اون اندیس عنصر رو حذف میکنیم با مرتبه ۱

مطمئنی؟

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

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

(06 بهمن ۱۳۹۳ ۰۱:۰۳ ب.ظ)ziba.O نوشته شده توسط:  خب حالا اگه اشاره گر به آخر داشته باشیم مرتبه ی زمانی حذف از آخر چی میشه؟

اگر اشاره گر آخر رو داشته باشیم

مثل این میمونه تو آرایه به ما اندازه کل آرایه رو داده باشن

و با دونستن اون اندیس عنصر رو حذف میکنیم با مرتبه ۱

مطمئنی؟

سوالا انقدر پیچ تو پیچ شد خودم پیچیدم
آقا اشاره گر به هرجا داشته باشیم اونجا دیگه نیاز به پیمایش نداره
خوب پس وقتی آخرو داریم مرتبش ۱ دیگه

(۰۶ بهمن ۱۳۹۳ ۰۱:۱۲ ب.ظ)tm.viper نوشته شده توسط:  سوالا انقدر پیچ تو پیچ شد خودم پیچیدم
آقا اشاره گر به هرجا داشته باشیم اونجا دیگه نیاز به پیمایش نداره
خوب پس وقتی آخرو داریم مرتبش ۱ دیگه

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

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

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

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

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

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

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

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

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

---

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

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

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

سلام.اگه اشاره گر به اخرین عنصر رو داشته باشیم و لیست هم یک طرفه باشه و بخوایم عنصر اخر رو حذف کنیم مرتبش $O(n)$ میشه

میگن دوطرفست که

---

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

(06 بهمن ۱۳۹۳ ۰۱:۱۲ ب.ظ)tm.viper نوشته شده توسط:  سوالا انقدر پیچ تو پیچ شد خودم پیچیدم

آقا اشاره گر به هرجا داشته باشیم اونجا دیگه نیاز به پیمایش نداره

خوب پس وقتی آخرو داریم مرتبش ۱ دیگه

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

اینجا یعنی کجا
اشاره گر داشته باشه یا نداشته باشه

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

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

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

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

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

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

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

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

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

---

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

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

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

سلام.اگه اشاره گر به اخرین عنصر رو داشته باشیم و لیست هم یک طرفه باشه و بخوایم عنصر اخر رو حذف کنیم مرتبش $O(n)$ میشه

میگن دوطرفست که

---

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

(06 بهمن ۱۳۹۳ ۰۱:۱۲ ب.ظ)tm.viper نوشته شده توسط:  سوالا انقدر پیچ تو پیچ شد خودم پیچیدم

آقا اشاره گر به هرجا داشته باشیم اونجا دیگه نیاز به پیمایش نداره

خوب پس وقتی آخرو داریم مرتبش ۱ دیگه

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

اینجا یعنی کجا
اشاره گر داشته باشه یا نداشته باشه

اینجا یعنی عنصر آخری که اشاره گر بهش داریمو میخوایم حذفش کنیم

مممممم

مرسی.من که مشکلم حل شد شمیم جون نمیدونم این تاپیکو خوندنی مشکلش حل میشه یا نه.

(۰۶ بهمن ۱۳۹۳ ۰۱:۴۷ ب.ظ)ziba.O نوشته شده توسط:  مرسی.من که مشکلم حل شد شمیم جون نمیدونم این تاپیکو خوندنی مشکلش حل میشه یا نه.

خدا رو شکر
سوال از لیست دارین حتما بزارین احتمال خیلی خیلی زیاد امسال ازش سوال میاد

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

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

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

---

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

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

سلام.اگه اشاره گر به اخرین عنصر رو داشته باشیم و لیست هم یک طرفه باشه و بخوایم عنصر اخر رو حذف کنیم مرتبش $O(n)$ میشه

اخه من ی نکته تو تست دیدم ک گفته :
حذف عنصر در لیست دوپیوندی ساده تر از لیست یکطرفه است چون در لیست دو پیوندی دیگر نیازی ب پیمایش نیس
پس با داشتن اشاره گر روی عنصر اخر میشه مرتبه۱!
ممنون از همه دوستان

---

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

(06 بهمن ۱۳۹۳ ۰۱:۴۷ ب.ظ)ziba.O نوشته شده توسط:  مرسی.من که مشکلم حل شد شمیم جون نمیدونم این تاپیکو خوندنی مشکلش حل میشه یا نه.

خدا رو شکر
سوال از لیست دارین حتما بزارین احتمال خیلی خیلی زیاد امسال ازش سوال میاد

اره یکی لیست پیوندی یکیم پشته وصف با درخت پوشا!
توروخدا نکته ای چیزی ازشون دارید بگید.

(۰۶ بهمن ۱۳۹۳ ۱۰:۱۳ ب.ظ)shamim_70 نوشته شده توسط:  اخه من ی نکته تو تست دیدم ک گفته :
حذف عنصر در لیست دوپیوندی ساده تر از لیست یکطرفه است چون در لیست دو پیوندی دیگر نیازی ب پیمایش نیس
پس با داشتن اشاره گر روی عنصر اخر میشه مرتبه۱!
ممنون از همه دوستان

سلام دوست عزیز منم با فرض یکطرفه بودن لیست گفتم $O(n)$ میشه

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

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