[Powered by Google Translate] প্রোগ্রামিং, আমরা প্রায়ই মান তালিকা চিত্রিত করা প্রয়োজন, যেমন ছাত্র হিসাবে একটি অধ্যায় এর নাম সর্বশেষ ব্যঙ্গ বা তাদের স্কোর. 

সি ভাষায়, ঘোষিত অ্যারে ব্যবহার করা যাবে যাও তালিকা সঞ্চয়. এটা একটি তালিকা উপাদান গনা সহজ সঞ্চিত একটি অ্যারের মধ্যে, এবং যদি আপনি অ্যাক্সেস প্রয়োজন অথবা ith তালিকা উপাদান সংশোধন করুন জন্য কিছু অবাধ সূচক আমি, যে ধ্রুব সময় এটি করা সম্ভব, কিন্তু অ্যারে অসুবিধেও আছে খুব,. 

যখন আমরা তাদের ডিক্লেয়ার, আমরা বলতে প্রয়োজন করছি আপ সামনে কত বড় তারা হয়, যে হয়, কতগুলি উপাদান তারা সঞ্চয় করতে পারেন এবং কিভাবে বড় এই উপাদান হল, যা তাদের টাইপ দ্বারা নির্ধারিত হয়. উদাহরণস্বরূপ, int-Arr (10) 10 আইটেম সঞ্চয় করতে পারেন যে কোন int মাপ. 

আমরা ঘোষণার পর একটি অ্যারে এর আকার পরিবর্তন করতে পারবেন না. আমরা একটি নতুন অ্যারে করতে হবে যদি আমরা আরো উপাদান সঞ্চয় করতে চান. কারণ এই সীমাবদ্ধতা উপস্থিত যে আমাদের প্রোগ্রাম সমগ্র অ্যারের সঞ্চয় হিসাবে একটি মেমরি সংলগ্ন অঞ্চলে. বলুন এই বাফার যেখানে আমরা আমাদের অ্যারের মধ্যে সংরক্ষণ করা হয়. অন্যান্য ভেরিয়েবল পর্যন্ত হতে পারে ডান পাশে অবস্থিত অ্যারে মেমরি, তাই আমরা নারা শুধু অ্যারের বড় করতে. 

কখনও কখনও আমরা অ্যারে এর তথ্য দ্রুত এক্সেস গতি ট্রেড চাই জন্য একটু আরো নমনীয়তা. লিঙ্ক তালিকা, অন্য একটি মৌলিক তথ্য গঠন লিখুন আপনার সাথে পরিচিত হতে না পারে. একটি উচ্চ স্তরের, একটি লিঙ্ক তালিকা নোডের একটি অনুক্রম তথ্য সঞ্চয় প্রতিটি অন্যান্য লিঙ্ক সঙ্গে সংযুক্ত করা হয়, তাই নাম 'লিঙ্ক তালিকা.' হিসাবে আমরা দেখতে পাবেন, নকশা মধ্যে এই পার্থক্য বিভিন্ন সুবিধার বাড়ে এবং অসুবিধেও যাও তুলনায় একটি অ্যারে. 

এখানে একটি খুব সহজ ইন্টিজার এর লিঙ্ক তালিকা জন্য সি কোড. আপনি যে আমরা প্রতিটি নোডের প্রতিনিধিত্ব আছে দেখতে পারেন একটি struct যা 2 জিনিস রয়েছে হিসাবে তালিকা, একটি পূর্ণসংখ্যা স্টোর নামক 'Val' এবং পরবর্তী নোডের একটি তালিকা লিঙ্ক যা আমরা একটি পয়েন্টার নামক হিসাবে চিত্রিত করা 'পরের.' এই ভাবে, আমরা সম্পূর্ণ তালিকা ট্র্যাক করতে পারেন শুধুমাত্র 1 ম নোড যাও একক পয়েন্টার, এবং তারপর আমরা পরের পয়েন্টার অনুসরণ করতে পারেন যাও 2nd নোড, যাও 3rd নোড, যাও 4th নোড, এবং তাই, যতক্ষণ না আমরা তালিকার শেষে পেতে. 

আপনি 1 এই সুবিধা আছে দেখতে পাবে উপর স্থির কাঠামো অ্যারে - সঙ্গে একটি লিঙ্ক তালিকা, আমরা সম্পূর্ণভাবে প্রয়োজন একটি মেমরি বড় তাল না. তালিকার 1 ম নোড মেমরির মধ্যে এই স্থানে বাস করতে পারে, এবং 2nd নোডের মধ্যে সমস্ত এখানে উপর উপায় হতে পারে. আমরা সমস্ত নোড কোন ব্যাপার পেতে যেখানে তারা মেমরি পারেন, কারণ শুরু 1st নোড এ, প্রতিটি নোডের এর পরের পয়েন্টার আমাদেরকে বলে ঠিক যেখানে পরবর্তী যান. 

উপরন্তু, আমরা সামনে বলতে আপ না কত বড় একটি লিঙ্ক তালিকা উপায় আমরা স্থির অ্যারে না হবে, যেহেতু আমরা একটি তালিকা নোডের যুক্ত করে যেতে পারবেন যতদিন নতুন নোডের জন্য মেমরি আছে কোথাও স্থান. অতএব, সংযুক্ত তালিকাগুলি পরিবর্তনশীলরূপে মাপ পরিবর্তন করা সহজ. বলুন, আমরা পরে আরো যোগ নোড প্রোগ্রামের প্রয়োজন আমাদের মধ্যে তালিকা. আমাদের তালিকায় উড়ে একটি নতুন নোডের মধ্যে সন্নিবেশ, সমস্ত আমরা করতে হবে তা হচ্ছে যে নোডের জন্য মেমরি বরাদ্দ করা, তথ্য মান অকস্মাৎ, এবং তারপর যেখানে আমরা যথাযথ পয়েন্টার সামঞ্জস্য স্থাপন করতে চান. 

উদাহরণস্বরূপ, যদি আমরা একটি নোডের মধ্যে স্থাপন করতে চেয়েছিলেন তালিকার 2nd এবং 3 য় নোড,  আমরা 2nd 3rd বা নোড এ সব সরানো আছে না. বলুন, আমরা এই লাল নোড করছি ঢোকাতে. সমস্ত আমরা কি চাই নতুন নোড এর পরের পয়েন্টার সেট 3rd নোড নির্দেশ এবং তারপর 2nd নোড এর পরের পয়েন্টার বৈদ্যুতিক তার লাগানো আমাদের নতুন নোডের দিকে নির্দেশ করে. সুতরাং, আমরা উড়ে আমাদের তালিকা মাপ পরিবর্তন করতে পারেন যেহেতু আমাদের কম্পিউটার ইন্ডেক্স উপর নির্ভর করে না, লিঙ্ক পয়েন্টার তাদের সঞ্চয় ব্যবহার করে বরং. 

তবে, একটা অসুবিধা লিঙ্ক তালিকা না যে, অসদৃশ একটি স্ট্যাটিক অ্যারে, কম্পিউটার ঠিক তালিকা মাঝখানে যাও না তিড়িং লাফ পারেন. যেহেতু কম্পিউটারের সাথে সংযুক্ত তালিকার প্রতিটি নোডের ভিজিট হয়েছে পরের এক পেতে, এটি আর একটি বিশেষ নোড খুঁজে নিতে যাচ্ছে তুলনায় এটি একটি অ্যারের হবে. যাও, তর্ক সম্পূর্ণ তালিকা সময় লাগে সমানুপাতিক তালিকার দৈর্ঘ্য, অথবা O (n) মধ্যে asymptotic স্বরলিপি. গড়ে, কোনো নোডের মধ্যে পৌঁছনোর এছাড়াও সময় লাগে সমানুপাতিক হবে যাও. 

এখন, আমি কি আসলে কিছু কোড লিখুন যে লিঙ্ক তালিকা সাথে কাজ করে. চলুন শুরু করা যাক বলতে আমরা একটি পূর্ণসংখ্যার এর লিঙ্ক তালিকা চাই. আমরা আমাদের তালিকা মধ্যে আবার একটি নোড উপস্থাপন করতে পারেন হিসাবে 2 ক্ষেত্রের সাথে একটি struct, একটি পূর্ণসংখ্যা মান নামক 'Val' এবং একটি তালিকা পরবর্তী নোডের পরবর্তী পয়েন্টার. ভাল, যথেষ্ট সহজ মনে হয়. 

চলুন শুরু করা যাক বলতে আমরা একটি ফাংশন লিখতে চান যা কপি করে প্রিন্ট আউট তালিকা এবং ঘোরে তালিকার সর্বশেষ নোডের মধ্যে মান সংরক্ষণ করা হয়. ভাল, মানে আমরা সমস্ত তালিকায় নোড, তর্ক করতে হবে গত এক পাবেন, কিন্তু যেহেতু আমরা যোগ করছি না বা কিছু মুছে ফেলা হচ্ছে, আমরা পরিবর্তন করতে ইচ্ছুক না তালিকায় পরবর্তী পয়েন্টার অভ্যন্তরীণ গঠন. 

সুতরাং, আমরা ট্র্যাভেরসাল জন্য একটি পয়েন্টার বিশেষভাবে করতে হবে যা আমরা 'ক্রলার.' ডাকবো এটা সমস্ত তালিকা উপাদানের মাধ্যমে হামাগুড়ি হবে দ্বারা পরবর্তী পয়েন্টার চেইন অনুসরণ. সমস্ত আমরা সঞ্চিত আছে 1st নোডের একটি পয়েন্টার, অথবা তালিকার 'মাথা'. 1 ম নোড যাও প্রধান পয়েন্ট. এই পার্টিশনটির ধরন পয়েন্টার টু নোডের মধ্যে এর. 

প্রকৃত তালিকা নোডের মধ্যে 1 ম পেতে, dereference যাও আমরা এই পয়েন্টার আছে, কিন্তু আগে আমরা dereference পারেন, আমরা যাচাই প্রয়োজন যদি পয়েন্টার হয় প্রথম নাল. এটি যদি নাল, তালিকা খালি, এবং আমরা একটি বার্তা যে, কারণ তালিকা খালি আউট প্রিন্ট করা উচিত, কোন শেষ হয় নোড. কিন্তু, এর যাক বলতে তালিকা ফাঁকা করা হবে না. এটি যদি না থাকে, তাহলে আমরা সম্পূর্ণ তালিকা মাধ্যমে ক্রল করবে যতক্ষণ না আমরা তালিকার শেষ নোড পেতে, এবং কিভাবে আমরা বলতে যদি আমরা তালিকা নোডের মধ্যে শেষ সময়ে খুঁজছেন তা করতে পারেন? 

ওয়েল, যদি একটি নোড এর পরের নাল পয়েন্টার হয়, আমরা জানি যে আমরা শেষে করছি গত পরের পয়েন্টার তালিকার যে কোন নির্দেশ পরের নোড আছে. এটা ভাল অনুশীলন সর্বদা শেষ নোড এর পরের নাল পয়েন্টার যাও সক্রিয়া রাখা একটি প্রমিত সম্পত্তি যা আমাদের সতর্ক করে যখন আমরা তালিকার শেষে পৌঁছেছেন আছে. 

সুতরাং, যদি ক্রলার → পরবর্তী নাল, মনে রাখবেন, যে তীর সিনট্যাক্স dereferencing জন্য একটি শর্টকাট একটি struct একটি পয়েন্টার তারপর, অ্যাক্সেস তার পরের ক্ষেত্রের সমতুল্য বিশ্রী যাও: (* ক্রলার). পরের. একবার আমরা শেষ নোড পাওয়া করেছি, আমরা ক্রলার → Val প্রিন্ট করতে চান, বর্তমান নোডের মধ্যে মান যা আমরা জানি শেষ জোড়া. অন্যথায়, যদি আমরা এখনও তালিকা নোডের মধ্যে শেষ না, আমরা তালিকায় পরবর্তী নোডের উপর সরানো আছে এবং যদি যে গত এক চেক. এই কাজের জন্য, আমরা আমাদের ক্রলার পয়েন্টার সেট বর্তমান নোড এর পরের মান নির্দেশ, যে হয়, তালিকায় পরবর্তী নোড. এই সেটিং দ্বারা এটি করা সম্ভব ক্রলার = ক্রলার → পরের. তারপর আমরা এই প্রক্রিয়া পুনরাবৃত্তি উদাহরণস্বরূপ একটি লুপ সঙ্গে,, শেষ পর্যন্ত আমরা খুঁজে নোড. সুতরাং, উদাহরণস্বরূপ, যদি ক্রলার মাথার প্রতি নির্দেশ ছিল, আমরা ক্রলার → পরবর্তী নির্দেশ ক্রলার সেট, যা 1st নোড পরবর্তী ক্ষেত্র হিসাবে একই. সুতরাং এখন, আমাদের ক্রলার 2nd নোড যাও প্রতি নির্দেশ করা হয়, এবং আবার,, আমরা একটি লুপ সঙ্গে এই পুনরাবৃত্তি, শেষ পর্যন্ত আমরা নোড পাওয়া করেছি, যে, যেখানে নোড এর পরের নাল পয়েন্টার যাও প্রতি নির্দেশ করা হয়. এবং সেখানে আমরা এটি আছে, আমরা তালিকায় করেছি শেষ নোড পাওয়া যায়, এবং তার মান মুদ্রণ, আমরা শুধু ক্রলার → Val ব্যবহার. 

ঢোঁড়ন হয়, কিন্তু কি সন্নিবেশ খারাপ, তাই না? আপনাকে বলতে আমরা 4 র্থ স্থান মধ্যে একটি পূর্ণসংখ্যা সন্নিবেশ করতে চান একটি পূর্ণসংখ্যা তালিকা. যে বর্তমান 3 য় এবং 4 র্থ নোডের মধ্যে হয়. আবার, আমরা তালিকা ঠিক আছে যাও, তর্ক করা 3 য় উপাদান, এক আমরা পরে ঢোকাতে করছি পেতে. সুতরাং, আমরা আবার একটি ক্রলার পয়েন্টার যাও, তর্ক তালিকা তৈরি, যদি আমাদের মাথা নাল পয়েন্টার হয় চেক, এবং যদি তা না, আমাদের মাথা নোড এ ক্রলার পয়েন্টার নির্দেশ. সুতরাং, আমরা 1 ম উপাদান করেন. আমরা 2 উপাদানের আরো এগিয়ে যান আমরা আগে সন্নিবেশ করতে পারেন, তাই আমরা একটি লুপ জন্য ব্যবহার করতে পারেন int i = 1; তোমার <3; তোমার + এবং লুপ প্রতিটি পুনরাবৃত্তির, আমাদের ক্রলার পয়েন্টার আগাম ফরোয়ার্ড 1 নোড দ্বারা চেক দ্বারা যদি বর্তমান নোড এর পরের ক্ষেত্রটি নাল, এবং যদি তা না, পরবর্তী নোডের আমাদের ক্রলার পয়েন্টার সরানো সেটিং দ্বারা এটি বর্তমান নোড এর পরের পয়েন্টার সমান. সুতরাং, আমাদের জন্য লুপ যাও যে বলে দুইবার, আমরা 3 য় নোড পৌঁছেছেন, এবং একবার আমাদের ক্রলার পয়েন্টার নোড পৌঁছেছে পরে যা আমরা আমাদের নতুন পূর্ণসংখ্যা সন্নিবেশ করতে চান, কিভাবে আমরা আসলে কি করবেন ঢোকাতে? 

ওয়েল, আমাদের নতুন ইন্টিজার আছে তালিকায় সন্নিবেশিত করা হিসাবে নিজস্ব নোড struct অংশ, যেহেতু এই সত্যিই নোড একটা ক্রম. সুতরাং, আসুন নোডের একটি নতুন পয়েন্টার করা বলা হয় 'new_node,' এবং এটি মেমরি বরাদ্দ করা যে এখন আমরা নির্দেশ সেট উপর নোডের জন্য নিজেই গাদা, এবং কতটা মেমরি বরাদ্দ করা প্রয়োজন আমরা কোথায় যাও? ওয়েল, একটি নোড মাপ, এবং আমরা পূর্ণসংখ্যা যে আমরা প্রবেশ করাতে চান তার Val ক্ষেত্র সেট করতে চান. চলুন শুরু করা যাক বলে, 6. এখন, আমাদের নোড পূর্ণসংখ্যা মান রয়েছে. এখানে ভাল অনুশীলন নতুন নোড এর পরের ক্ষেত্রের আরম্ভ যাও যাও নাল নির্দেশ, কিন্তু এখন কি? 

আমরা তালিকা অভ্যন্তরীণ কাঠামো পরিবর্তন করতে হবে এবং পরের পয়েন্টার তালিকা এর বিদ্যমান থাকা 3 য় এবং 4 র্থ নোড. যেহেতু পরের পয়েন্টার তালিকা অনুযায়ী, নির্ধারণ এবং যেহেতু আমরা আমাদের নতুন নোডের মধ্যে ঢোকাতে করছি সরাসরি তালিকা মধ্যম, এটি একটি চতুর বিট হতে পারেন. কারণ, মনে রাখবেন, আমাদের কম্পিউটার শুধুমাত্র নোড তালিকায় অবস্থান জানে কারণ পূর্ববর্তী পরবর্তী নোডের মধ্যে সংরক্ষিত পয়েন্টার দেয়া হল. সুতরাং, যদি আমরা এই অবস্থানে কোন ট্র্যাক হারিয়ে ফেলেন, আমাদের তালিকায় পরবর্তী পয়েন্টার এক পরিবর্তন করে বলে, উদাহরণস্বরূপ, আমরা বলতে পরিবর্তন 3rd নোড এর পরের ক্ষেত্র এখানে কিছু নোড দিকে নির্দেশ করে. আমরা এর ভাগ্য আউট, কারণ আমরা না কি হতে চাই যেখানে কোনো তালিকার বাকি খুঁজে ধারণা আছে, এবং যে সম্ভবত খুব খারাপ. সুতরাং, আমরা সত্যিই আদেশ সম্পর্কে সতর্কতা অবলম্বন করা আবশ্যক আছে যা আমরা সন্নিবেশ সময় আমাদের পরবর্তী পয়েন্টার নিপূণভাবে. 

সুতরাং, এই প্রক্রিয়া সহজ, আমি কি বলে যে আমাদের প্রথম 4 নোড , A, B, C, ও D নামক পয়েন্টার শৃঙ্খল প্রতিনিধিত্বমূলক তীরযুক্ত, হয় যে নোডের সাথে সংযুক্ত করুন. সুতরাং, আমরা আমাদের প্রয়োজন নতুন নোডের মধ্যে সন্নিবেশ নোডের মধ্যে সি এবং ডি এটা সঠিক অনুক্রমে এটা গুরুতর, এবং আমি আপনাকে দেখাতে হবে কেন. 

চলুন কুপথ প্রথমে এটা তাকান. আরে, আমরা জানতে পারি যে নতুন নোডের যাও সি ডান পরে আসা হয়েছে, তাই আসুন সি এর পরের পয়েন্টার সেট যাও যাও new_node নির্দেশ. ঠিক আছে, মনে হয় ঠিক আছে, আমরা শুধু দ্বারা সমাপ্ত এখন পর্যন্ত আছে : D নতুন নোড এর পরের পয়েন্টার পয়েন্ট তৈরি, কিন্তু অপেক্ষা, যে কিভাবে আমরা কি করতে পারি? শুধু যে আমাদের বলতে যেখানে ডি ছিল পারে, ছিল পরের পয়েন্টার পূর্বে C-এ সংরক্ষণ করা কিন্তু আমরা যে পয়েন্টার rewrote নতুন নোডের দিকে নির্দেশ করে, তাই আমরা আর কোনো সুরুক যেখানে ডি মেমরি হয় আছে, এবং আমরা তালিকা বাকি নষ্ট করেছি. . সব ভাল নেই 

সুতরাং কিভাবে, আমরা কি করে এই অধিকার? প্রথমত, নতুন নোড এর ডি এ পয়েন্টার পরবর্তী নির্দেশ এখন, উভয় নতুন নোড এর এবং সি এর পরের পয়েন্টার একই নোড, D-প্রতি নির্দেশ করা হয়, কিন্তু যে সূক্ষ্ম. এখন আমরা সি এর নতুন নোডের এ পয়েন্টার পরবর্তী নির্দেশ করতে পারেন. তাই আমরা কোনো তথ্য হারানো ছাড়া এই করেছেন. কোড ইন, সি বর্তমান নোড যে ট্র্যাভেরসাল পয়েন্টার ক্রলার যাও প্রতি নির্দেশ করা হয়, এবং D নোড বর্তমান নোড এর পরের ক্ষেত্র দ্বারা তীক্ষ্ন যাও প্রতিনিধিত্ব করেন, বা ক্রলার → পরের. সুতরাং, প্রথম আমরা নতুন নোড এর পরের পয়েন্টার সেট ক্রলার → পরের দিকে নির্দেশ করে, একই ভাবে আমরা বলেছেন new_node এর পরের পয়েন্টার উচিত চিত্রণ মধ্যে D-র দিকে নির্দেশ করে. তারপর, আমরা বর্তমান নোড এর পরের পয়েন্টার সেট করতে পারেন আমাদের নতুন নোড, ঠিক যেমন আমরা সি আঁকার মধ্যে new_node নির্দেশ অপেক্ষা করতে হয়েছিল. এখন ক্রম সবকিছু, আর আমরা না হারান নি কোনো তথ্য ট্র্যাক, এবং আমরা ঠিক করতে পারবেন তালিকা মাঝখানে আমাদের নতুন নোডের সোঁটা ছাড়া গোটা ব্যাপারটাই পুনর্নির্মাণ বা এমনকি কোনো উপাদান নড়ন আমাদের কাছে আছে একটি নির্দিষ্ট দৈর্ঘ্যের অ্যারের সঙ্গে ছিল. 

সুতরাং, সংযুক্ত তালিকাগুলি একটি মৌলিক, কিন্তু গুরুত্বপূর্ণ, গতিশীল ডাটা স্ট্রাকচার যা উভয় সুবিধার এবং অসুবিধেও আছে তুলনায় যাও অ্যারে এবং অন্যান্য ডাটা স্ট্রাকচার, এবং হিসাবে প্রায়ই কম্পিউটার বিজ্ঞানের ক্ষেত্রে, এটা যখন প্রতিটি টুল ব্যবহার জানা গুরুত্বপূর্ণ, যাতে আপনি সঠিক কাজের জন্য ডান হাতিয়ার বাছাই করতে পারেন. 

আরো অনুশীলনের জন্য, ফাংশন লেখার চেষ্টা একটি লিঙ্ক তালিকা থেকে মুছে দিন নোড - ক্রম যা আপনি নতুন করে সাজানো সম্পর্কে সতর্কতা অবলম্বন করা আবশ্যক মনে রাখা আপনার পরের পয়েন্টার যে আপনি আপনার তালিকা একটি তাল হারাবেন না তা নিশ্চিত করার জন্য - অথবা একটি ফাংশন একটি লিঙ্ক তালিকা বিভিন্ন নোডের গণনা, অথবা একটি মজার এক, একটি লিঙ্ক তালিকা বিভিন্ন নোডের মধ্যে সমস্ত আদেশ বিপরীত. 

আমার নাম জ্যাকসন STEINKAMP, এই CS50.