జావా లింక్డ్‌లిస్ట్

హాయ్! అన్ని తాజా పాఠాలు అర్రేలిస్ట్‌కు అంకితం చేయబడ్డాయి . ఈ డేటా నిర్మాణం చాలా సౌకర్యవంతంగా మరియు ఉపయోగకరంగా ఉంటుంది. ఇది చాలా పనులను నిర్వహించగలదు. కానీ జావాలో చాలా ఇతర డేటా స్ట్రక్చర్‌లు ఉన్నాయి. ఎందుకు? అన్నింటికంటే మించి, టాస్క్‌ల పరిధి అపారమైనది మరియు విభిన్న పనులకు అత్యంత సమర్థవంతమైన డేటా స్ట్రక్చర్‌లు భిన్నంగా ఉంటాయి. ఈ రోజు మనం కొత్త నిర్మాణాన్ని కలుస్తాము: Java LinkedList , డబుల్-లింక్ చేయబడిన జాబితా. ఇది ఎలా నిర్వహించబడుతుందో చూద్దాం, దీనిని డబుల్-లింక్డ్ అని ఎందుకు పిలుస్తారు, ఇది అర్రేలిస్ట్ నుండి ఎలా భిన్నంగా ఉందో చూద్దాం . జావా లింక్డ్‌లిస్ట్‌లోని మూలకాలు వాస్తవానికి ఒకే గొలుసులోని లింక్‌లు. డేటాతో పాటు, ప్రతి మూలకం మునుపటి మరియు తదుపరి అంశాలకు సూచనలను నిల్వ చేస్తుంది. ఈ సూచనలు మిమ్మల్ని ఒక మూలకం నుండి మరొక మూలకానికి తరలించడానికి అనుమతిస్తాయి. మీరు ఒకదాన్ని సృష్టించే విధానం ఇలా ఉంది:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

అవుట్‌పుట్: [హలో వరల్డ్! నా పేరు ఎర్ల్, నేను జావాను ప్రేమిస్తున్నాను, నేను కెనడాలో నివసిస్తున్నాను] మా జాబితా ఎలా ఉంటుందో ఇక్కడ ఉంది: కొత్త మూలకాన్ని ఎలా జోడించాలో చూద్దాం. ఇది add() పద్ధతిని ఉపయోగించి చేయబడుతుంది .

earlBio.add(str2);

కోడ్‌లోని పాయింట్ వద్ద, మా జాబితా ఒక మూలకాన్ని కలిగి ఉంటుంది: స్ట్రింగ్ str1 . చిత్రంలో తదుపరి ఏమి జరుగుతుందో చూద్దాం: ఫలితంగా, జాబితా యొక్క ఈ నోడ్‌లలో నిల్వ చేయబడిన తదుపరి మరియు మునుపటి లింక్‌ల ద్వారా str2 మరియు str1 లింక్ అవుతాయి : ఇప్పుడు మీరు డబుల్-లింక్డ్ జాబితా యొక్క ప్రధాన ఆలోచనను అర్థం చేసుకోవాలి. ఈ లింక్‌ల గొలుసు ఖచ్చితంగా లింక్డ్‌లిస్ట్ మూలకాలను ఒకే జాబితాగా చేస్తుంది. అర్రేలిస్ట్ వలె కాకుండా , లింక్డ్‌లిస్ట్‌లో శ్రేణి లేదా లోపల శ్రేణి లాంటిదేమీ లేదు. అర్రేలిస్ట్‌తో ఏదైనా (బాగా, చాలా వరకు) పని అంతర్గత శ్రేణితో పని చేయడం వరకు తగ్గుతుంది. జావా లింక్డ్‌లిస్ట్‌తో ఏదైనా పనిలింక్‌లను మార్చడం కోసం దిమ్మదిరిగింది. జాబితా మధ్యలో ఒక మూలకాన్ని జోడించడం ద్వారా ఇది చాలా స్పష్టంగా చూడవచ్చు:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

మీరు చూడగలిగినట్లుగా, ఓవర్‌లోడ్ చేయబడిన యాడ్() పద్ధతి కొత్త అంశం కోసం నిర్దిష్ట సూచికను పేర్కొనడానికి మిమ్మల్ని అనుమతిస్తుంది. ఈ సందర్భంలో, మేము str1 మరియు str3 మధ్య స్ట్రింగ్ str2ని జోడించాలనుకుంటున్నాము . ఇది అంతర్గతంగా జరుగుతుంది: అంతర్గత లింక్‌లను మార్చిన తర్వాత, str2 జాబితాకు విజయవంతంగా జోడించబడింది: ఇప్పుడు మొత్తం 3 అంశాలు కనెక్ట్ చేయబడ్డాయి. మీరు గొలుసులోని మొదటి మూలకం నుండి చివరి మరియు వెనుకకు తదుపరి లింక్ ద్వారా తరలించవచ్చు . కాబట్టి, చొప్పించడంలో మేము చాలా సౌకర్యంగా ఉన్నాము, అయితే మూలకాలను తీసివేయడం గురించి ఏమిటి? సూత్రం సరిగ్గా అదే. మేము తీసివేయబడుతున్న మూలకం యొక్క "ఎడమ మరియు కుడికి" రెండు మూలకాలలోని లింక్‌లను అప్‌డేట్ చేస్తాము:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

మేము ఇండెక్స్ 1తో ఐటెమ్‌ను తొలగిస్తే ఏమి జరుగుతుందో ఇక్కడ ఉంది (ఇది జాబితా మధ్యలో ఉంది): లింక్‌లను నవీకరించిన తర్వాత, మేము కోరుకున్న ఫలితాన్ని పొందుతాము: అర్రేలిస్ట్‌లోని తీసివేత ఆపరేషన్ వలె కాకుండా , ఇక్కడ శ్రేణి మూలకాలను మార్చడం లేదా చేయవలసిన అవసరం లేదు రకమైన ఏదైనా. మేము కేవలం str1 మరియు str3 కోసం లింక్‌లను అప్‌డేట్ చేస్తాము . అవి ఇప్పుడు ఒకదానికొకటి సూచిస్తాయి మరియు str2 లింక్‌ల గొలుసు నుండి " వదిలిపోయింది " మరియు ఇకపై జాబితాలో భాగం కాదు.

పద్ధతుల యొక్క అవలోకనం

లింక్డ్‌లిస్ట్ అర్రేలిస్ట్‌తో చాలా సాధారణ పద్ధతులను కలిగి ఉంది . ఉదాహరణకు, రెండు తరగతులకు add() , remove() , indexOf() , clear() , కలిగి() (ఒక అంశం జాబితాలో ఉందో లేదో సూచిస్తుంది), set() (ఇప్పటికే ఉన్న మూలకాన్ని భర్తీ చేస్తుంది) మరియు పరిమాణం () . వాటిలో చాలా అంతర్గతంగా విభిన్నంగా పనిచేసినప్పటికీ (మేము add() మరియు remove() లతో కనుగొన్నట్లుగా ), తుది ఫలితం ఒకే విధంగా ఉంటుంది. ఏదేమైనా, లింక్డ్‌లిస్ట్ జాబితా ప్రారంభం మరియు ముగింపుతో పని చేయడానికి ప్రత్యేక పద్ధతులను కలిగి ఉంది, వీటిని అర్రేలిస్ట్ కలిగి లేదు:

• addFirst() , addLast() : జాబితా ప్రారంభం/ముగింపుకు మూలకాన్ని జోడించడానికి ఈ పద్ధతులు

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

అవుట్‌పుట్: [కార్{మోడల్='ఫెరారీ 360 స్పైడర్'}, కార్{మోడల్='బుగట్టి వేరాన్'}, కార్{మోడల్='లంబోర్ఘిని డయాబ్లో'}] [కార్{మోడల్='ఫోర్డ్ మోండియో'}, కార్{మోడల్=' Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}] మేము జాబితాలో అగ్రస్థానంలో "ఫోర్డ్"తో ముగుస్తాము , మరియు ముగింపులో "ఫియట్".

• peekFirst() , peekLast() : పద్ధతులు జాబితాలో మొదటి/చివరి మూలకాన్ని తిరిగి అందిస్తాయి. జాబితా ఖాళీగా ఉంటే అవి శూన్యంగా తిరిగి వస్తాయి.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

అవుట్‌పుట్: కార్{మోడల్='ఫెరారీ 360 స్పైడర్'} కార్{మోడల్='లంబోర్ఘిని డయాబ్లో'}

• pollFirst() , pollLast() : ఈ పద్ధతులు జాబితాలోని మొదటి/చివరి ఎలిమెంట్‌ను అందించి, జాబితా నుండి తీసివేయబడతాయి. జాబితా ఖాళీగా ఉంటే అవి శూన్యంగా తిరిగి వస్తాయి

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

అవుట్‌పుట్: Car{model='Ferrari 360 Spider'} Car{model='Lamborghini Diablo'} జాబితాలో ఏమి మిగిలి ఉంది? [కార్{మోడల్='బుగట్టి వేరాన్'}]

• toArray() : ఈ పద్ధతి జాబితా అంశాలను కలిగి ఉన్న శ్రేణిని అందిస్తుంది

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

అవుట్‌పుట్: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] లింక్డ్‌లిస్ట్ ఎలా పని చేస్తుందో మరియు దాని సంస్థ ArrayList నుండి ఎలా విభిన్నంగా ఉందో ఇప్పుడు మనకు తెలుసు . లింక్డ్‌లిస్ట్ ఉపయోగించడం వల్ల కలిగే ప్రయోజనాలు ఏమిటి ? అన్నింటికంటే, జాబితా మధ్యలో పని చేస్తున్నప్పుడు మేము ప్రయోజనం పొందుతాము. లింక్డ్‌లిస్ట్ మధ్యలో చొప్పించడం మరియు తీసివేత కార్యకలాపాలు అర్రేలిస్ట్‌లో కంటే చాలా సరళంగా ఉంటాయి . మేము పొరుగు మూలకాల లింక్‌లను అప్‌డేట్ చేస్తాము మరియు లింక్‌ల గొలుసు నుండి అవాంఛిత మూలకం "పడిపోతుంది". కానీ అర్రేలిస్ట్‌లో , మనం తప్పక

• తగినంత స్థలం ఉందో లేదో తనిఖీ చేయండి (చొప్పించేటప్పుడు)
• కాకపోతే, మేము కొత్త శ్రేణిని సృష్టించి, అక్కడ డేటాను కాపీ చేస్తాము (చొప్పించేటప్పుడు)
• మేము మూలకాన్ని తీసివేస్తాము/చొప్పిస్తాము మరియు అన్ని ఇతర మూలకాలను కుడి/ఎడమ వైపుకు (ఆపరేషన్ రకాన్ని బట్టి) తరలిస్తాము. మరియు ఈ ప్రక్రియ యొక్క సంక్లిష్టత జాబితా పరిమాణంపై ఎక్కువగా ఆధారపడి ఉంటుంది. 10 ఎలిమెంట్‌లను కాపీ/తరలించడం ఒక విషయం మరియు మిలియన్ ఎలిమెంట్‌లతో అదే చేయడం మరొకటి.

మరో మాటలో చెప్పాలంటే, మీ ప్రోగ్రామ్‌లో జాబితా మధ్యలో చొప్పించడం/తొలగింపు కార్యకలాపాలు సర్వసాధారణంగా ఉంటే, లింక్డ్‌లిస్ట్ అర్రేలిస్ట్ కంటే వేగంగా ఉండాలి .

సిద్ధాంత పరంగా

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

అవుట్‌పుట్: లింక్డ్‌లిస్ట్ తీసుకున్న సమయం (మిల్లీసెకన్లలో) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

అవుట్‌పుట్: అర్రేలిస్ట్ తీసుకున్న సమయం (మిల్లీసెకన్లలో) = 181 అది ఊహించనిది! లింక్డ్‌లిస్ట్ మరింత సమర్థవంతంగా ఉండేలా మేము ఒక ఆపరేషన్ చేసాము : జాబితా మధ్యలో 100 ఐటెమ్‌లను ఇన్‌సర్ట్ చేయడం. మరియు మా జాబితా చాలా పెద్దది: 5,000,000 మూలకాలు. అర్రేలిస్ట్ ప్రతి చొప్పించడంతో రెండు మిలియన్ ఐటెమ్‌లను మార్చవలసి ఉంటుంది! ఎలా గెలిచింది? ముందుగా, ఎలిమెంట్‌లను యాక్సెస్ చేయడానికి అర్రేలిస్ట్‌కి అవసరమైన సమయం స్థిరంగా ఉంటుంది (స్థిరంగా). మీరు వ్రాసేటప్పుడు

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

అప్పుడు ArrayList [2_000_000] అనేది ఒక నిర్దిష్ట మెమరీ చిరునామా (అన్ని తరువాత, జాబితా అంతర్గత శ్రేణిని కలిగి ఉంటుంది). కానీ, లింక్డ్‌లిస్ట్‌కు శ్రేణి లేదు. ఇది లింక్‌ల గొలుసుతో పాటు మూలకం సంఖ్య 2_000_000 కోసం శోధిస్తుంది. లింక్డ్‌లిస్ట్ కోసం, ఇది మెమరీ చిరునామా కాదు, కానీ ఇంకా చేరుకోవాల్సిన లింక్: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next. తదుపరి _ , ArrayListకి ప్రాప్యత చేయడానికి ఖచ్చితమైన మెమరీ చిరునామా ఇప్పటికే తెలుసు, కానీ లింక్డ్‌లిస్ట్ ఇప్పటికీ "అక్కడకు చేరుకోవాలి". రెండవది, అర్రేలిస్ట్ యొక్క నిర్మాణం ఉందిస్వయంగా. ప్రత్యేక అంతర్గత ఫంక్షన్ ( System.arrayCopy() ) అంతర్గత శ్రేణిని విస్తరిస్తుంది మరియు అన్ని మూలకాలను కాపీ చేస్తుంది మరియు బదిలీ చేస్తుంది. ఇది చాలా వేగంగా ఉంటుంది, ఎందుకంటే ఇది ఈ నిర్దిష్ట పని కోసం ఆప్టిమైజ్ చేయబడింది. కానీ మీరు నిర్దిష్ట సూచికను "పొందాల్సిన" అవసరం లేనప్పుడు, లింక్డ్‌లిస్ట్ విజేతగా ఉంటుంది. మేము జాబితా ప్రారంభంలోనే చొప్పించామని అనుకుందాం. అక్కడ మిలియన్ ఎలిమెంట్‌లను చొప్పించడానికి ప్రయత్నిద్దాం:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

అవుట్‌పుట్: మిల్లీసెకన్లలో ఫలితం: 43448 మిల్లీసెకన్లలో ఫలితం: 107 ఇప్పుడు మనం పూర్తిగా భిన్నమైన ఫలితాన్ని పొందుతాము! ArrayList 43 సెకన్ల కంటే ఎక్కువ సమయం జాబితా ముందు భాగంలో ఒక మిలియన్ ఐటెమ్‌లను ఇన్‌సర్ట్ చేసింది, అయితే లింక్డ్‌లిస్ట్ దీన్ని 0.1 సెకన్లలో చేయగలిగింది! లింక్డ్‌లిస్ట్ ఇక్కడ ప్రయోజనం పొందింది, ఎందుకంటే ఇది ప్రతిసారీ జాబితా మధ్యలో లింక్‌ల గొలుసు ద్వారా అమలు చేయవలసిన అవసరం లేదు. ఇది వెంటనే జాబితా ప్రారంభంలో అవసరమైన సూచికను కనుగొంటుంది, కాబట్టి విభిన్న అల్గోరిథం ఇప్పటికే ఒక ప్రయోజనం. :) నిజానికి, " అర్రేలిస్ట్ వర్సెస్ లింక్డ్‌లిస్ట్ " చర్చ చాలా విస్తృతంగా ఉంది మరియు ప్రస్తుత స్థాయిలో మేము దాని గురించి లోతుగా డైవ్ చేయము. మీరు గుర్తుంచుకోవలసిన ప్రధాన విషయం ఇది:

• అన్ని సైద్ధాంతిక ప్రయోజనాలు ఏదైనా నిర్దిష్ట సేకరణ ఎల్లప్పుడూ వాస్తవానికి పని చేయదు (జాబితా మధ్యలో ఉన్న ఉదాహరణతో మేము దీనిని చూశాము)
• సేకరణను ఎంచుకునే విషయంలో విపరీతమైన స్థితిని అవలంబించవద్దు (" అర్రేలిస్ట్ ఎల్లప్పుడూ వేగవంతమైనది. దాన్ని ఉపయోగించండి మరియు మీరు తప్పు చేయలేరు. లింక్డ్‌లిస్ట్‌ని చాలా కాలంగా ఎవరూ ఉపయోగించడం లేదు").

లింక్డ్‌లిస్ట్ రచయిత, జాషువా బ్లాచ్ కూడా ఇదే విషయాన్ని చెప్పారు. :) అయినప్పటికీ, ఈ దృక్పథం 100% సరైనది కాదు మరియు మేము దీని గురించి మనల్ని మనం ఒప్పించుకున్నాము. మా మునుపటి ఉదాహరణలో, లింక్డ్‌లిస్ట్ 400 (!) రెట్లు వేగంగా ఉంది. మరొక విషయం ఏమిటంటే, లింక్డ్‌లిస్ట్ ఉత్తమ ఎంపిక అయిన కొన్ని పరిస్థితులు నిజంగా ఉన్నాయి . కానీ అవి ఉనికిలో ఉన్నాయి మరియు సరైన సమయంలో లింక్డ్‌లిస్ట్మీకు అందంగా రివార్డ్ చేయవచ్చు. పాఠం ప్రారంభంలో మనం ఏమి చెప్పామో మర్చిపోవద్దు: అత్యంత సమర్థవంతమైన డేటా నిర్మాణాలు వేర్వేరు పనులకు భిన్నంగా ఉంటాయి. మీ టాస్క్‌కి సంబంధించిన అన్ని షరతులు మీకు తెలియనంత వరకు ఏ డేటా నిర్మాణం ఉత్తమంగా ఉంటుందో 100% ఖచ్చితంగా చెప్పడం అసాధ్యం. మీరు ఈ సేకరణల గురించి తర్వాత మరింత తెలుసుకుంటారు, ఇది ఎంపికను సులభతరం చేస్తుంది. కానీ సరళమైన మరియు అత్యంత ప్రభావవంతమైన ఎంపిక ఎల్లప్పుడూ ఒకే విధంగా ఉంటుంది: మీ ప్రోగ్రామ్‌లో ఉపయోగించిన వాస్తవ డేటాపై రెండింటినీ ప్రయత్నించండి. అప్పుడు మీరు రెండు రకాల జాబితాలు ఎలా పని చేస్తారో మీరే చూడగలరు మరియు మీరు ఖచ్చితంగా తప్పు చేయరు. :) మీరు నేర్చుకున్న వాటిని బలోపేతం చేయడానికి, మీరు మా జావా కోర్సు నుండి వీడియో పాఠాన్ని చూడాలని మేము సూచిస్తున్నాము