معرفی لیست‌های پیوندی در پایتون

 #  درک linked lists در پایتون

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

قبل از اینکه به عمق بیشتری در مورد اینکه لیست های پیوندی چیستند و چگونه می توانید از آنها استفاده کنید برویم، ابتدا باید نحوه ساختار آنها را بیاموزید. هر عنصر از یک لیست پیوندی یک گره(node) نامیده می شود و هر گره دارای دو فیلد(field) متفاوت است:

1. data حاوی مقداری است که باید در گره ذخیره شود.
2. Next حاوی ارجاع به گره بعدی در لیست است.

در اینجا یک گره معمولی می بینید:

لیست پیوندی مجموعه ای از گره ها است. اولین گره سر(head) نامیده می شود و به عنوان نقطه شروع برای هر تکرار در لیست استفاده می شود. آخرین گره باید مرجع بعدی خود را به None برای تعیین انتهای لیست داشته باشد. در اینجا چگونه به نظر می رسد:

اکنون که می‌دانید یک لیست پیوندی چگونه ساختار می‌یابد، آماده‌اید تا به چند مورد کاربرد عملی برای آن نگاه کنید.

ویدیو پیشنهادی: ویدیو آموزش لیست ها در پایتون

 +  کاربردهای عملی

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

 +  صف‌ها(Queues) و پشته‌ها(Stacks)

صف ها و پشته ها فقط در نحوه بازیابی عناصر متفاوت هستند. برای یک صف، از رویکرد First-In/First-Out (FIFO) استفاده می کنید. این بدان معناست که اولین عنصر درج شده در لیست اولین عنصری است که بازیابی می شود:

در نمودار بالا می توانید عناصر جلو و عقب صف را مشاهده کنید. هنگامی که عناصر جدیدی را به صف اضافه می کنید، آنها به انتهای صفحه می روند. هنگامی که عناصر را بازیابی می کنید، آنها از جلوی صف گرفته می شوند.

برای یک پشته، از رویکرد Last-In/First-Out (LIFO) استفاده می کنید، به این معنی که آخرین عنصر درج شده در لیست اولین عنصری است که بازیابی می شود:

در نمودار بالا می بینید که اولین عنصر درج شده در پشته (شاخص 0) در پایین و آخرین عنصر درج شده در بالا قرار دارد. از آنجایی که پشته ها از رویکرد LIFO استفاده می کنند، آخرین عنصر درج شده (در بالا) اولین عنصری است که بازیابی می شود.

به دلیل نحوه درج و بازیابی عناصر از لبه‌های صف و پشته، لیست‌های پیوندی یکی از راحت‌ترین راه‌ها برای پیاده‌سازی این ساختارهای داده است. نمونه هایی از این پیاده سازی ها را در ادامه مقاله خواهید دید.

ویدیو پیشنهادی: ویدیو آموزش deque در پایتون

 +  گراف‌ها(Graphs)

از نمودارها می توان برای نشان دادن روابط بین اشیاء یا نمایش انواع مختلف شبکه ها استفاده کرد. به عنوان مثال، یک نمایش بصری از یک نمودار - مثلاً یک گراف غیر چرخه ای جهت دار (DAG) - ممکن است به این صورت باشد:

روش های مختلفی برای پیاده سازی نمودارهایی مانند موارد بالا وجود دارد، اما یکی از رایج ترین آنها استفاده از لیست مجاورت(adjacency list) است. فهرست مجاورت، در اصل، فهرستی از لیست‌های پیوندی است که در آن هر رأس نمودار در کنار مجموعه‌ای از رئوس متصل ذخیره می‌شود:

در جدول بالا، هر رأس(vertex) نمودار شما در ستون سمت چپ فهرست شده است. ستون سمت راست شامل یک سری لیست های مرتبط است که رئوس دیگر متصل به راس مربوطه را در ستون سمت چپ ذخیره می کند. این فهرست مجاورت را می‌توان با استفاده از دیکشنری نیز به صورت کد نشان داد:

>>> graph = {
...     1: [2, 3, None],
...     2: [4, None],
...     3: [None],
...     4: [5, 6, None],
...     5: [6, None],
...     6: [None]
... }

کلیدهای این دیکشنری رئوس منبع هستند و مقدار هر کلید یک لیست است. این لیست معمولاً به صورت یک لیست پیوندی پیاده سازی می شود.

از نظر سرعت و حافظه، اجرای نمودارها با استفاده از لیست مجاورت در مقایسه با ماتریس مجاورت(adjacency matrix) بسیار کارآمد است. به همین دلیل است که لیست های پیوندی برای اجرای نمودار بسیار مفید هستند.

ویدیو پیشنهادی: ویدیو آموزش ماژول queue در پایتون

 #  معرفی collections.deque

در پایتون، یک شیء خاص در ماژول collections وجود دارد که می‌توانید از آن برای لیست‌های پیوندی به نام deque (تلفظ "deck") استفاده کنید که مخفف صف دو طرفه است.

collections.deque از پیاده سازی یک لیست پیوندی استفاده می کند که در آن می توانید به عناصری از ابتدا یا انتهای یک لیست با عملکرد O(1) ثابت دسترسی داشته باشید، درج کنید یا حذف کنید.

روش‌های زیادی وجود دارد که به‌طور پیش‌فرض با یک شی deque همراه هستند. با این حال، در این مقاله فقط به تعدادی از آنها اشاره می‌کنید که بیشتر برای افزودن یا حذف عناصر هستند.

ابتدا باید یک لیست پیوندی ایجاد کنید. برای انجام این کار با deque می توانید از کد زیر استفاده کنید:

>>> from collections import deque
>>> deque()
deque([])

کد بالا یک لیست پیوندی خالی ایجاد می کند. اگر می‌خواهید آن را در هنگام ایجاد پر کنید، می‌توانید به عنوان ورودی آن را تکرار کنید:

>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])

>>> deque('abc')
deque(['a', 'b', 'c'])

>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])

هنگام مقداردهی اولیه یک شی deque، می توانید هر تکرار شونده را به عنوان ورودی ارسال کنید، مانند یک رشته (همچنین یک تکرار) یا لیستی از اشیاء.

اکنون که می دانید چگونه یک شی deque ایجاد کنید، می توانید با افزودن یا حذف عناصر با آن تعامل داشته باشید. می توانید یک لیست پیوندی abcde ایجاد کنید و یک عنصر جدید f را مانند این اضافه کنید:

>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])

>>> llist.pop()
'f'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

هر دو append() و pop() عناصر را از سمت راست لیست پیوند داده شده اضافه یا حذف می کنند. با این حال، می‌توانید از deque برای افزودن یا حذف سریع عناصر از سمت چپ یا سر فهرست نیز استفاده کنید:

>>> llist.appendleft("z")
>>> llist
deque(['z', 'a', 'b', 'c', 'd', 'e'])

>>> llist.popleft()
'z'

>>> llist
deque(['a', 'b', 'c', 'd', 'e'])

افزودن یا حذف عناصر از هر دو انتهای لیست با استفاده از شی deque بسیار ساده است. اکنون شما آماده یادگیری نحوه استفاده از collections.deque برای اجرای یک صف یا یک پشته هستید.

ویدیو پیشنهادی: آموزش کار با mysql در پایتون

 +  چطور صف‌ها و پشته‌ها را ایجاد کنیم؟

همانطور که در بالا آموختید، تفاوت اصلی بین یک صف و یک پشته در نحوه بازیابی عناصر از هر یک است. در مرحله بعد، نحوه استفاده از collections.deque برای پیاده سازی هر دو ساختار داده را خواهید یافت.

 +  صف‌ها(Queues)

با صف‌ها، می‌خواهید مقادیری را به لیست اضافه کنید (صف)، و زمانی که زمان‌بندی مناسب باشد، می‌خواهید عنصری را که طولانی‌ترین زمان در لیست بوده است (dequeue) حذف کنید. به عنوان مثال، یک صف در یک رستوران مد روز و کاملاً رزرو شده را تصور کنید. اگر می‌خواهید یک سیستم منصفانه برای نشستن مهمانان پیاده‌سازی کنید، باید با ایجاد یک صف و اضافه کردن افراد به هنگام ورود شروع کنید:

>>> from collections import deque
>>> queue = deque()
>>> queue
deque([])

>>> queue.append("Mary")
>>> queue.append("John")
>>> queue.append("Susan")
>>> queue
deque(['Mary', 'John', 'Susan'])

حالا شما Mary، John و Susan را در صف دارید. به یاد داشته باشید که از آنجایی که صف ها FIFO هستند، اولین فردی که وارد صف می شود باید اولین نفری باشد که از آن خارج می شود.

حالا تصور کنید مدتی می گذرد و چند جدول در دسترس است. در این مرحله می خواهید افراد را به ترتیب صحیح از صف حذف کنید. به این صورت این کار را انجام می دهید:

>>> queue.popleft()
'Mary'

>>> queue
deque(['John', 'Susan'])

>>> queue.popleft()
'John'

>>> queue
deque(['Susan'])

هر بار که popleft() را فرا می‌خوانید، عنصر head را از لیست پیوندی حذف می‌کنید و یک صف واقعی را تقلید می‌کنید.

ویدیو پیشنهادی: ویدیو آموزش آبجکت ellipsis در پایتون

 +  پشته‌ها(Stacks)

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

تصور کنید که در حال ایجاد قابلیت تاریخچه یک مرورگر وب هستید که در آن هر صفحه ای که کاربر بازدید می کند ذخیره می کند تا بتواند به راحتی به گذشته برگردد. فرض کنید اینها اقداماتی هستند که یک کاربر تصادفی در مرورگر خود انجام می دهد:

1. از وب سایت Real Python بازدید کنید
2. به مقاله Pandas: How to Read and Write Files میرود
3. روی پیوندی برای Reading and Writing CSV Files in Python کلیک می‌کند

اگر می‌خواهید این رفتار را در یک پشته ترسیم کنید، می‌توانید کاری شبیه به این انجام دهید:

>>> from collections import deque
>>> history = deque()

>>> history.appendleft("https://realpython.com/")
>>> history.appendleft("https://realpython.com/pandas-read-write-files/")
>>> history.appendleft("https://realpython.com/python-csv/")
>>> history
deque(['https://realpython.com/python-csv/',
       'https://realpython.com/pandas-read-write-files/',
       'https://realpython.com/'])

در این مثال، شما یک شی تاریخ خالی ایجاد کرده اید و هر بار که کاربر از یک سایت جدید بازدید می کند، آن را با استفاده از appendleft() به متغیر history خود اضافه می کنید. با انجام این کار اطمینان حاصل شد که هر عنصر جدید به سر لیست پیوند داده شده اضافه می شود.

حال فرض کنید که کاربر پس از خواندن هر دو مقاله، می‌خواهد به صفحه اصلی پایتون واقعی برگردد تا مقاله جدیدی را برای خواندن انتخاب کند. با دانستن اینکه یک پشته دارید و می خواهید عناصر را با استفاده از LIFO حذف کنید، می توانید کارهای زیر را انجام دهید:

>>> history.popleft()
'https://realpython.com/python-csv/'

>>> history.popleft()
'https://realpython.com/pandas-read-write-files/'

>>> history
deque(['https://realpython.com/'])

با استفاده از popleft()، عناصر را از سر لیست پیوندی حذف کردید تا زمانی که به صفحه اصلی برسید.

از مثال‌های بالا، می‌توانید ببینید که چقدر می‌تواند مفید باشد که collections.deque در جعبه ابزار خود داشته باشید، بنابراین دفعه بعد که یک چالش مبتنی بر صف یا پشته برای حل دارید، مطمئن شوید که از آن استفاده کنید.