தொடர் பட்டியல் (Linked lists)

தொடர் பட்டியல் என்பது ஒரு எளிதான தரவு வடிவம். சுலபமாக பல ஆயிரக்கணக்கான மதிப்புகளை சேமிக்க இந்த தொடர் பட்டியல் பயன்படுத்தலாம்.

தொடர் பட்டியல் அவதாரங்கள்

இந்த தொடர் பட்டியல் இரண்டு வகையாக அமையும்: ஒருபடை தொடர் பட்டியல் (singly linked list) மற்றும் இருபடை(doubly linked list) இவை கீழே படங்களில் காணலாம். இதனையும் தாண்டி வட்டம் தொடர் பட்டியல் (circular linked list) என்றும் செய்யலாம் இதனை கடைசியில் காண்போம்.

408px-singly-linked-list-svg

படம் 1: ஒருபடை தொடர் பட்டியல் (singly linked list). இதன் முதல் தலை நுனி ‘12’ என்ற மதிப்பை கொண்டது. இதன் ‘அடுத்த’ மதிப்பு ‘99’ மதிப்பு கொண்ட நுனியின் விலாசத்தை கொண்டது. மேலும் ‘99’ நுனி ‘37’ என்ற மதிப்பு கொண்ட நுனியின் விலாசம் கொண்டது. ‘37’ நுனி என்பது கடைசி நுனி என்பதால் இதற்க்கு அடுத்து மதிப்பு காலி என கொண்டது. இந்த ‘அடுத்து’ என்ற இணைப்பே ‘12’ நுனியில் தொடங்கி ‘37’ வரை செல்லும் அம்சத்தை தொடர் பட்டியல் என்று ஆகும் படி இந்த தரவு வடிவத்திற்கு அளிக்கிறது.

610px-doubly-linked-list-svg

படம் 2: படம் 1-ஐ போலவே தொடர் பட்டியல் ஆனால் ‘அடுத்து’ மதிப்பை போலவே கூடுதலாக ‘முந்தைய’ என்ற மதிப்பையும் ஒவ்வொரு நுனியும் கொண்டது. இதன் காரணமாக இதனை ‘இருபடை தொடர் பட்டியல்’.

 

தொடர் பட்டியல் அமைப்பு

தொடர் பட்டியல் என்பது நுனிகள் என்பதால் உருவாக்கப்பட்டது; இவை ஒருன்றுடன் ஒன்று ‘அடுத்து’ என்ற மதிப்பில் இணைக்க பெற்று முழுமையாக தொடர் என்று உருவம் எடுக்கிறது. இது உதிரி பூக்களை மாலையாக கோர்ப்பது போல என்று நினைத்து கொள்ளலாம்.

# நுனி உருவாக்குதல்

நிரல்பாகம் ஒருபடை_நுனி( மதிப்பு )

      நு = {“அடுத்து” : [], “மதிப்பு” : மதிப்பு  }

      பின்கொடு நு

முடி

# நுனியின் அடுத்து விலாசத்தை மற்றோரு நுனியில் அமைத்தல் /

நிரல்பாகம் ஒருபடை_இணை( நுனி_முதல், நுனி_அடுத்து  )

      நுனி_முதல் [“அடுத்து”] = நுனி_அடுத்து

      பின்கொடு நுனி_அடுத்து

முடி

தொடர் பட்டியலில் அணுகுதல்

தொடர் பட்டியலின் முதல் நுனியை “தலை நுனி” என்று பெயரிடுவோம். இந்த தலை நுனியை மட்டும் நாம் கொண்டு முழு பட்டியலை ஒவ்வொன்றாக அணுகலாம். எப்படி ? நுனியில் “அடுத்து” என்ற நுனி விலாசம் உள்ளதை வைத்து நுனிக்கு செல்லலாம். இதனையே பலமுறை – அதாவது அடுத்து என்பதன் மதிப்பு காலி ஆகும் வரை – செய்தால் முழு பட்டியலையும் தலை நுனியில் இருந்து கடைசி நுனிவரை ஒவ்வொன்றாக அணுகலாம். இதனை “ஒருபடை_அணுகு()” என்ற நிரல்பாகம் நிரல்படுத்தும்.

தொடர் பட்டியலில் தேடல்

சரி – இப்ப இந்த பட்டியலில் ஒரு குறிப்பிட்ட மதிப்பு உள்ளதா என்று எப்படி தேடுவது ? இந்த செயல்முறையை நம்ம “ஒருபடை தொடர் பட்டியல் தேடல்” என்று பெயரிடுவோம். தேடல் என்பது பட்டியலில் உள்ள ஒவ்வொரு நுனியையும் அணுகி (அணுகுதல் என்ற நிரல்பாகம் கீழே எழுதப்பட்டதைப்போல்) குறிப்பிட்ட மதிப்பிற்கு சமமாக உள்ளதா என்று பார்க்கவேண்டும்.

# ஒருபடை தொடர் பட்டியலை வரிசையில் அணுகுதல்

நிரல்பாகம் ஒருபடை_அணுகு( நுனி  )

   நுனி_அடுத்து = []

   காலி =  []

   @(    நுனி != காலி  ) வரை  

       #பதிப்பி “முதிப்பு  => “,

       பதிப்பி நுனி [“மதிப்பு”]

       நுனி_அடுத்து = நுனி [“அடுத்து”]

       நுனி = நுனி_அடுத்து

   முடி

   பின்கொடு  நுனி_அடுத்து

முடி

தேடிய ‘குறிப்பிட்ட மதிப்பு’ கிடைக்காவிட்டால் -1 என்ற மதிப்பு பின்கொடுக்கப்படும்; கிடைத்தால், தலை நுனியில் இருந்து தூரத்தை  வரிசை எண் என்று பின்கொடுக்கப்படும்

நிரல்பாகம் ஒருபடை_தேடு ( நுனி, குறிப்பிட்ட_மதிப்பு   )

   நுனி_அடுத்து = []

   காலி =  []

   வரிசை_எண்  = 1

   @(    நுனி != காலி  ) வரை

       @( நுனி [“மதிப்பு”] == குறிப்பிட்ட_மதிப்பு ) ஆனால்

           பின்கொடு வரிசை_எண்        

       முடி

        நுனி_அடுத்து = நுனி [“அடுத்து”]

        நுனி = நுனி_அடுத்து

        வரிசை_எண் = வரிசை_எண் + 1

   முடி

   பின்கொடு  -1

முடி

 

# நுனி உருவாக்குதல்

நு12 = ஒருபடை_நுனி( 12 )

நு99 = ஒருபடை_நுனி( 99 )

நு37 = ஒருபடை_நுனி( 37 )

 

# நுனியின் அடுத்து விலாசத்தை மற்றோரு நுனியில் அமைத்தல் /

ஒருபடை_இணை( நு12, நு99 )

ஒருபடை_இணை( நு99, நு37 )

 

# ஒருபடை தொடர் பட்டியலை வரிசையில் அணுகுதல்

ஒருபடை_அணுகு( நு12 )

#சாவே இல்லாத வீட்டிலே கைப்பிடி கடுகு  கிடைக்குமா ?

பதிப்பி ஒருபடை_தேடு(நு12, 10) 

பதிப்பி ஒருபடை_தேடு(நு12, 37)

இதன் வெளியீடு :  12, 99, 37. முழு நிரல் இங்கு.

இந்த மாதிரி தொடர் பட்டியலில் பல கேள்விகளை எழுப்பலாம், உதாரணத்திற்கு:

  1. இரண்டு தொடர்பட்டியலை எப்படி இணைப்பது ?
  2. ஒரு தொடர்பட்டியலில் குறிப்பிட்ட மதிப்பு எத்தனை முரை அவதானிக்கிறது ?
  3. தொடர்பட்டியலை முன்னுக்கு பின் எப்படி வேகமாக மாற்றுவது ?
  4. இரு தொடர் பட்டியலில் உள்ள பொதுவான மதிப்புகளை கண்டு எடுக்க முடியுமா ?
  5. அணிகள் (arrays) என்பதற்கும் தொடர் பட்டியல் என்பதற்கும் என்ன வித்யாசம் ?

இதனை போல கேள்விகளை பயிற்சிக்கு கேட்டு கொண்டே போகலாம். அனால் நீங்கள் இந்த இரண்டு புத்தகங்களை நேரம் கிடைக்கும் சமயம் கட்டாயம் படித்தால் எல்லாம் விளங்கும்.

  1. “Introduction to algorithms” by Cormen, Leiserson, Rivest, and Stein. MIT press இங்கு.
  2. “The Algorithm Design Manual” by Steven Skiena. இங்கு

இதை இரண்டையுமே நீங்கள் கரைத்து குடித்துவிட்டால் உங்களுக்கு நிரலாக்க திரையில் கிராக்கி அமோகமாக விளங்கும். அப்படி கார்பொரேட் கைதியாக இருக்கவேண்டாம் என்று வீரப்பாக இருந்தால் இந்த புத்தகத்தில் உள்ள லட்டு, ஜிலேபி இனிப்புகளை இன்பமாக அனுபவியுங்கள்.

மேலும் அடுத்த வாரம்.

-முத்து

கவனத்திற்கு: தொடர் பட்டியல் படங்கள் விக்கிபீடியா, புத்தக அட்டைகள் பதிப்பகத்திற்கு சொந்தம்; எழுத்து பிழைகள் எல்லாமே என்னோடது.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s