>> [সঙ্গীত বাজাচ্ছি]
ডগ লয়েড: ঠিক আছে.
তাই আপনি শুধু যে কর্ম সমাপ্ত হলে একেলা সংযুক্ত তালিকা দুঃখিত ভিডিও
আমি একটি উপর আপনি বাম বন্ধ একটি cliffhanger বিট.
কিন্তু আমি আপনাকে শেষ করার জন্য এখানে এসেছি খুশি দোকর-লিঙ্ক তালিকা গল্প.
>> আপনার কাছ থেকে প্রত্যাহার হলে তাই যে ভিডিও, আমরা বললাম
এককভাবে সংযুক্ত সম্পর্কে তালিকা আমাদের ক্ষমতা উপস্থিত
তথ্য মোকাবেলা করতে যেখানে উপাদানের সংখ্যা
বা আইটেম সংখ্যা একটি তালিকা প্রসারণ বা সঙ্কুচিত করতে পারেন.
আমরা এখন মোকাবেলা করতে পারেন যে ভালো কিছু, যেখানে
আমরা অ্যারে সঙ্গে তা মোকাবেলা করতে পারে.
>> কিন্তু তারা এক ভোগা না গুরুতর সীমাবদ্ধতা যা
একটি এককভাবে সংযুক্ত যে সাথে তালিকায়, আমরা শুধুমাত্র কখনও সরাতে পারেন
তালিকায় মাধ্যমে একটি একক দিক.
এবং শুধুমাত্র প্রকৃত অবস্থা যেখানে যে একটি সমস্যা হতে পারে
ছিল যখন আমরা করার চেষ্টা করা হয়েছে একটি একক উপাদান মুছে দিন.
এবং আমরা এমনকি কিভাবে এটা করবেন আলোচনা করা হয়নি pseudocode মধ্যে একটি এককভাবে সংযুক্ত তালিকার.
এটা অবশ্যই হয় doable কিন্তু এটি একটি ঝগড়া একটি বিট হতে পারে.
আপনি নিজেকে খুঁজে সুতরাং যদি একটি অবস্থা যেখানে
আপনি মোছার চেষ্টা করছেন তালিকা থেকে একক উপাদান
বা এটা করা যাচ্ছে আপনি মোছার হবে যে
থেকে একক উপাদান তালিকায়, আপনি চাইতে পারেন
ব্যবহারের বিষয়ে বিবেচনা করার জন্য একটি দোকর-লিঙ্ক পরিবর্তে একটি একেলা সংযুক্ত তালিকা তালিকা.
দোকর-লিঙ্ক তালিকা আপনি অনুমতি দেয়, কারণ সম্মুখে এবং পিছনের দিকে উভয় সরাতে
পরিবর্তে তালিকা মাধ্যমে শুধু এগিয়ে তালিকার মাধ্যমে
মাত্র এক অতিরিক্ত উপাদান যুক্ত করে আমাদের কাঠামো সংজ্ঞা
দোকর-লিঙ্ক তালিকা নোডের জন্য.
>> আবার, আপনি যাচ্ছেন না হলে একক উপাদান মুছে ফেলার করা
তালিকার থেকে আমরা যোগ করছি কারণ আমাদের কাঠামো একটি অতিরিক্ত ক্ষেত্র
সংজ্ঞা, নোড নিজেদের দোকর-লিঙ্ক তালিকা জন্য
বড় হতে যাচ্ছি.
তারা নিতে যাচ্ছেন মেমরি বেশি বাইট আপ.
আর যদি তাই হয় এই কিছু নয় আপনি, করতে হবে চলুন
আপনি এটা সিদ্ধান্ত নিতে পারে বন্ধ অধিকারী না বাণিজ্য
অতিরিক্ত ব্যয় করা আছে মেমরি বাইট প্রয়োজন
একটি দোকর-লিঙ্ক তালিকা জন্য আপনি না হন তাহলে যাচ্ছে একক উপাদান মুছে ফেলার করা.
কিন্তু তারা শান্ত হন অন্যান্য জিনিসের জন্য.
>> আমি আগেই বলেছি, আমরা শুধু যোগ আছে আমাদের কাঠামো এক একক ক্ষেত্র
এই ধারণা definition-- পূর্ববর্তী পয়েন্টার.
একটি একেলা লিঙ্ক তালিকা সুতরাং, আমরা , মান এবং পরের পয়েন্টার আছে
তাই দোকর-লিঙ্ক তালিকা শুধু আছে একটি উপায় হিসেবে পিছনের দিকে সরানো.
>> এখন এককভাবে সংযুক্ত মধ্যে তালিকায় ভিডিও, আমরা বললাম
এই সম্পর্কে পাঁচটি আপনাকে হতে হবে প্রধান জিনিষ
পারবেন সংযুক্ত তালিকার সঙ্গে কাজ করতে করতে.
এবং এর মধ্যে সবচেয়ে আসলে জন্য এটি একটি দোকর-লিঙ্ক তালিকা যে
সত্যিই একটি বড় লাফ নয়.
আমরা এখনও ঠিক করে দিয়ে অনুসন্ধান করতে পারেন শুরু থেকে অগ্রগতিশীল শেষ করতে.
আমরা এখনও আউট একটি নোড তৈরি করতে পারেন পাতলা বায়ু, প্রায় একই ভাবে.
আমরা বেশ তালিকা মুছে দিতে পারেন খুব বেশী একই ভাবে.
শুধুমাত্র কিছু যে subtly, ভিন্ন
সত্যিই, ঢোকাতে হয় তালিকায় নতুন নোডের,
এবং পরিশেষে আমরা মোছার বিষয়ে কথা বলতে পারবেন পাশাপাশি তালিকা থেকে একটি একক উপাদান.
আবার, অনেক সুন্দর অন্য তিনটি, আমরা করছি
তাদের সম্পর্কে কথা বলতে যাচ্ছি না এই মুহূর্তে তারা শুধু করছি কারণ
ধারনা খুব ছোটখাট tweaks আলোচনা এককভাবে সংযুক্ত তালিকা ভিডিওতে.
>> সুতরাং আসুন একটি নতুন নোডের মধ্যে সন্নিবেশ করা যাক একটি দোকর-লিঙ্ক তালিকা মধ্যে.
আমরা এই কাজ সম্পর্কে সায়ীদ পাশাপাশি তালিকা এককভাবে সংযুক্ত,
কিন্তু অতিরিক্ত একটি দম্পতি আছে দোকর-লিঙ্ক তালিকা সাথে ক্যাচ.
আমরা [আছেন? ক্ষণস্থায়ী?] মাথা এখানে তালিকা এবং কিছু নির্বিচারে মান,
এবং আমরা নতুন মাথা পেতে চান এই ফাংশন আউট তালিকার.
এটি একটি dllnode তারকা ফেরৎ কেন.
সেজন্য পদক্ষেপ কি হয়?
তারা আবার, অনুরূপ তালিকা এককভাবে সংযুক্ত করতে
এক অতিরিক্ত যোগে.
আমরা একটি নতুন জন্য স্থান বরাদ্দ করতে চান নোড এবং চেক এটা বৈধ কি না নিশ্চিত করতে.
আমরা যে নোড ভরাট করতে চান যাই হোক না কেন তথ্য দিয়ে আমরা
এটা লাগাতে চান.
শেষ জিনিস আমরা যা করতে হবে আমরা যা করতে হবে অতিরিক্ত জিনিস, rather--
পূর্ববর্তী পয়েন্টার ঠিক করা হয় তালিকার পুরানো মাথার.
মনে রাখবেন যে, কারণ এর দ্বিগুণ-লিঙ্ক তালিকা,
আমরা অগ্রসর হতে পারে এবং backwards-- যা
প্রতিটি নোডের আসলে যে স্থানটিকে মানে দুই অন্যান্য নোড পরিবর্তে শুধুমাত্র এক.
আর তাই আমরা ঠিক করতে হবে তালিকার পুরানো মাথা
নতুন প্রধান অনগ্রসর নির্দেশ কিছু ছিল যা লিঙ্ক তালিকা,
আমরা আগে কি করতে হত না.
আর আগের মত, আমরা শুধু একটি ফিরতি তালিকার নতুন মাথার পয়েন্টার.
>> তাই এখানে একটি তালিকা.
আমরা এই তালিকায় 12 সন্নিবেশ করাতে চান.
চিত্রটি লক্ষ্য করুন যে কিছুটা ভিন্ন.
প্রতিটি নোডের তিনটি ক্ষেত্রের রয়েছে তথ্য, এবং লাল পরবর্তী পয়েন্টার,
এবং নীল পূর্ববর্তী পয়েন্টার.
কিছুই, 15 নোড আগে আসে তাই তার আগের নাল পয়েন্টার হয়.
এটি তালিকার শুরুতে.
এটা আগে কিছুই নেই.
আর কিছুই, 10 নোড পরে আসে এবং তাই এটি পরবর্তী পয়েন্টার পাশাপাশি নাল হয়.
>> তাই আসুন এই তালিকায় 12 যোগ দিন.
আমরা নোড জন্য [শ্রবণাতীত] স্থান প্রয়োজন.
আমরা এটা নিয়ে 12 ভিতরে রাখা.
এবং তারপর আবার, আমরা সত্যিই হতে হবে সতর্কতা অবলম্বন চেইন বিরতি না.
আমরা পুনর্বিন্যস্ত করতে চান সঠিক অনুক্রমে পয়েন্টার.
এবং কখনও কখনও যে mean-- পারে আমরা বিশেষ করে দেখতে পাবেন
delete-- সাথে আমরা কিছু আছে কি যে অপ্রয়োজনীয় পয়েন্টার, কিন্তু এটা ঠিক আছে.
>> তাই আমরা প্রথম কাজ করতে চান না?
আমি কথা বলতে চাই জিনিষ আপনি সম্ভবত উচিত
কি 12 এর পয়েন্টার ভরাট হয় নোড আপনি অন্য কেহ স্পর্শ করার পূর্বে.
তাই কি 12 পরবর্তী নির্দেশ যাচ্ছে?
15.
কি 12 আগে আসে?
কিছুই.
এখন আমরা পূরণ করেছি 12 অতিরিক্ত তথ্য
তাই এটি পূর্ববর্তী, পরবর্তী, এবং মান আছে.
>> এখন আমরা থাকতে পারে 15-- এই অতিরিক্ত আমরা বিষয়ে কথা হয় ধাপে
ফিরে 12 15 পয়েন্ট থাকতে পারে.
আর এখন আমরা মাথা সরাতে পারেন লিঙ্ক তালিকা এছাড়াও 12 হতে.
সুতরাং এটা বেশ অনুরূপ কি আমরা একেলা সংযুক্ত তালিকা সঙ্গে কাজ হয়েছে,
এর অতিরিক্ত পদক্ষেপ ছাড়া তালিকার পুরানো মাথা সংযোগ
তালিকায় নতুন প্রধান করায় মনোযোগ দিয়েছি.
>> এখন এর পরিশেষে মুছে দিন একটি লিঙ্ক তালিকা থেকে একটি নোড.
সুতরাং আসুন আমরা আছে বলা যাক অন্য কিছু ফাংশন যে
আমরা মুছে ফেলতে চান একটি নোড খুঁজে বের করা হয় এবং ঠিক করতে আমাদের একটি পয়েন্টার দিয়েছেন
আমরা মুছে ফেলতে চান যে নোড.
আমরা এমনকি বলতে need-- না মাথা এখনও বিশ্বব্যাপী ঘোষিত হয়.
আমরা এখানে মাথা প্রয়োজন হবে না.
এই সমস্ত ফাংশন করছে আমরা করেছি ঠিক নোড আমরা একটি পয়েন্টার পাওয়া
পরিত্রাণ পেতে চান.
এর এটা পরিত্রাণ পেতে চলুন শুরু করা যাক.
এটা নিয়ে অনেক সহজ দোকর-লিঙ্ক.
এটা আসলে First-- মাত্র কয়েক জিনিষ.
আমরা শুধু পার্শ্ববর্তী ঠিক করা প্রয়োজন নোড 'পয়েন্টার তারা উপর লাফালাফি যাতে
নোড আমরা মুছে ফেলতে চান.
এবং তারপর আমরা যে নোড মুছে দিতে পারেন.
তাই আবার, আমরা শুধু এখানে দিয়ে যাচ্ছেন.
আমরা দৃশ্যত যে সিদ্ধান্ত নিয়েছি আমরা নোড এক্স মুছে ফেলতে চান
এবং আবার, আমি কি করছি উপায় আছে দ্বারা এখানে করছেন
একটি জন্য একটি সাধারণ ক্ষেত্রে হয় মাঝখানে যে নোড.
একটি দম্পতি আছে অতিরিক্ত আদেশ সহকারে যে আপনি
আপনি মুছে ফেলার করছেন বিবেচনা করতে হবে তালিকার খুব প্রারম্ভে
অথবা তালিকার একেবারে শেষ.
বিশেষ একটি দম্পতি আছে কোণ ক্ষেত্রে সেখানে মোকাবেলা করতে.
>> তাই এই কোনো নোডের মধ্যে মোছার জন্য কাজ করে তালিকার এক মাঝখানে যে
এগিয়ে একটি বৈধ পয়েন্টার আছে এবং অনগ্রসর একটি বৈধ পয়েন্টার,
বৈধ পূর্ববর্তী ও পরবর্তী পয়েন্টার.
আবার আপনি যদি কাজ করে যাচ্ছি প্রান্ত দিয়ে, আপনি
ঐ সব ব্যবস্থা করতে হবে সামান্য ভিন্নভাবে,
এবং আমরা চলুন না এখন যে বিষয়ে কথা বলতে.
কিন্তু আপনি সম্ভবত পারেন প্রয়োজন কি চিন্তা
এই ভিডিও দেখার দ্বারা শুধু কাজ করতে হবে.
>> সুতরাং আমরা বিচ্ছিন্ন থাকেন এক্স এক্স নোড আমরা তালিকা থেকে মুছে ফেলতে চান.
আমরা কি করবো?
প্রথমত, আমরা নতুন করে সাজানো প্রয়োজন বাইরে পয়েন্টার.
আমরা নতুন করে সাজানো প্রয়োজন 9 এর পরের 13 উপর লাফালাফি করা
এবং বিন্দু 10-- যা আমরা ঠিক করেছি কি.
আর আমরা উদাহরণ প্রয়োজন 10 এর আগের পুনর্বিন্যস্ত
পরিবর্তে 13 নির্দেশকারী 9 নির্দেশ করার.
>> তাই আবার, এই ছিল সঙ্গে শুরু করতে চিত্রটি.
এই আমাদের চেইন ছিল.
আমরা, 13 উপর লাফালাফি করতে হবে কিন্তু আমরা সংরক্ষণ করা প্রয়োজন
তালিকায় অখণ্ডতা.
আমরা কোনো হারাতে চাই না উভয় দিক তথ্য.
তাই আমরা নতুন করে সাজানো প্রয়োজন পয়েন্টার সাবধানে
তাই আমরা এ সব শৃঙ্খল বিরতি না.
>> তাই আমরা 9 ​​এর পরের পয়েন্টার বলতে পারেন একই জায়গায় স্থানটিকে
যে তেরো এর পরবর্তী পয়েন্টার ডান এখন পয়েন্ট.
আমরা শেষ পর্যন্ত কারণ 13 উপর লাফালাফি করতে চান যাচ্ছে.
তাই যেখানেই থাকুন না কেন 13 পয়েন্ট পরের, আপনি নয়টি পরিবর্তে সেখানে নির্দেশ করতে চান.
সুতরাং যে যে.
এবং তারপর যেখানে 13 পয়েন্ট ফিরে যাও, 13 আগে আসে যাই হোক না কেন,
আমরা নির্দেশ 10 চান যে পরিবর্তে 13.
আপনি অনুসরণ এখন, যদি লক্ষ্য তীর, আমরা 13 ড্রপ করতে পারেন
আসলে কোন তথ্য হারানো ছাড়া.
আমরা, তালিকা অখণ্ডতা রাখা করেছি ফরোয়ার্ড এবং অনগ্রসর উভয় চলন্ত.
এবং তারপর আমরা শুধু বাছাই করতে পারেন একটি সামান্য বিট এটা পরিষ্কার
একসঙ্গে তালিকা কাছে দ্বারা.
সুতরাং আমরা পুনর্বিন্যাস উভয় পাশ পয়েন্টার.
এবং তারপর আমরা এক্স মুক্ত 13 অন্তর্ভুক্ত যে নোড
এবং আমরা ধারাবাহিক ভঙ্গ করা হয়নি.
তাই আমরা ভাল করেনি.
>> এখানে লিঙ্ক তালিকায় চূড়ান্ত নোট.
সুতরাং singly- উভয় এবং দোকর-লিঙ্ক তালিকা, হিসাবে আমরা দেখা করেছি,
সমর্থন সত্যিই দক্ষ সন্নিবেশ এবং উপাদান মুছে ফেলার.
আপনি অনেক সুন্দর করতে পারেন ধ্রুব সময় এটা.
আমরা কি মুছে ফেলতে কী করতে হয়েছিল একটি উপাদান আগে শুধু এই একটি দ্বিতীয়?
আমরা এক পয়েন্টার সরানো.
আমরা অন্য পয়েন্টার সরানো.
আমরা X-- তিনটি অপারেশন গ্রহণ মুক্ত.
এটা সবসময় তিনটি অপারেশন লাগে একটি নোড মুক্ত করতে যে নোড মুছে দিন.
>> আমরা কিভাবে সন্নিবেশ না?
ওয়েল, আমরা শুধু সবসময় আছেন শুরুতে উপর tacking
আমরা দক্ষতার ঢোকাতে করছি.
সুতরাং আমরা rearrange-- প্রয়োজন এটা যদি তার উপর নির্ভর করে
একটি singly- বা দোকর-লিঙ্ক তালিকায়, আমরা তিনটি না করার প্রয়োজন হতে পারে
অথবা চারটি অপারেশন সর্বোচ্চ.
কিন্তু আবার, এটা সবসময় তিন বা চার হবে.
এটা কিভাবে অনেক ব্যাপার না উপাদান, আমাদের তালিকায় আছে
এটা সবসময় তিন বা চার operations-- এর শুধু মুছে ফেলার সর্বদা মত
তিন বা চার অপারেশন.
এটা ধ্রুব সময়.
সুতরাং যে সত্যিই দারুণ.
>> অ্যারে দিয়ে, আমরা সেটিই ছিল সন্নিবেশ সাজানোর মত কিছু.
আপনি সম্ভবত যে সন্নিবেশ প্রত্যাহার সাজান একটি ধ্রুবক সময় এলগরিদম নয়.
এটা আসলে বেশ ব্যয়বহুল.
সুতরাং এই ঢোকাতে জন্য অনেক বেশি ভালো হয়.
কিন্তু আমি হিসাবে উল্লেখ করেছে তালিকায় ভিডিও এককভাবে সংযুক্ত,
আমরা এখানে একটি downside পেয়েছিলাম খুব, ডান থাকেন?
আমরা ক্ষমতা হারিয়ে ফেলেছি এলোমেলোভাবে উপাদান অ্যাক্সেস.
আমরা আমি উপাদান চার নম্বর চান, বলতে পারি না একটি লিঙ্ক তালিকা বা উপাদান সংখ্যা 10
একই ভাবে যে আমরা যা করতে পারেন একটি অ্যারের সাথে যে কি
বা আমরা শুধু সরাসরি সূচক পারেন আমাদের অ্যারের এর উপাদান মধ্যে.
>> আর তাই একটি অনুসন্ধান করার চেষ্টা একটি লিঙ্ক তালিকার মধ্যে উপাদান
অনুসন্ধানের important-- হয় তাহলে এখন রৈখিক সময় লাগতে পারে.
তালিকায় আর পায়, এটা এক অতিরিক্ত পদক্ষেপ নিতে পারে
তালিকার প্রতিটি উপাদান জন্য যাতে আমরা যা খুঁজছেন তা খুঁজে পেতে.
তাই বাণিজ্য বন্ধ আছে.
একটি প্রো একটি বিট আছে এখানে এবং বিরূদ্ধে উপাদান.
>> এবং দোকর-লিঙ্ক তালিকা না হয় ডাটা স্ট্রাকচার সমন্বয় সর্বশেষ ধরনের
আমরা সম্পর্কে আলোচনা করব যে সব মৌলিক বিল্ডিং গ্রহণ
সি ব্লকের একটি একসঙ্গে নির্বাণ.
আসলে, আমরা করতে পারেন, কারণ এমনকি এই বেশী ভালো না
একটি ডাটা স্ট্রাকচার নির্মাণ যে আপনি মাধ্যমে অনুসন্ধান করতে সক্ষম হতে পারে
ধ্রুব সময় খুব.
কিন্তু অন্য ভিডিওতে যে আরও.
>> আমি ডগ লয়েড আছি.
এটি CS50.