प्रौद्योगिकी साझेदारी

LinkedList तथा ​​लिङ्क्ड् सूची

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. ArrayList इत्यस्य दोषाः

ArrayList इत्यस्मिन् कस्मिन् अपि स्थाने तत्त्वानि सम्मिलितुं वा विलोपयन्ते सति, भवद्भिः सम्पूर्णानि अनन्तरं तत्त्वानि अग्रे वा पश्चात् वा गन्तुं आवश्यकानि सन्ति तथा च कार्यक्षमता तुल्यकालिकरूपेण न्यूना भवति अतः ArrayList कस्मिन् अपि स्थाने सम्मिलितुं विलोपयितुं च उपयुक्ता नास्ति स्थितिः दृश्यम् । अतः: LinkedList, लिङ्क्ड् सूचीसंरचना, जावासङ्ग्रहेषु प्रवर्तते ।

2. लिङ्क् कृतसूची

२.१ लिङ्क्ड् सूचीयाः अवधारणा संरचना च

लिङ्क्ड् सूची भौतिकरूपेण अनिरन्तरं भण्डारणसंरचना भवति, तथा च लिङ्क्ड् सूचीयां सन्दर्भलिङ्क् क्रमेण दत्तांशतत्त्वानां तार्किकक्रमः प्राप्तः भवति

२.२ लिङ्क्ड् सूचीयाः कार्यान्वयनम्

1. शीर्षकं सम्मिलनविधिः addFirst() .

  1. public void addFirst(int data) {
  2.         ListNode node = new ListNode(data);
  3.         node.next = head;
  4.         head = node;
  5.     }

2. पुच्छं सम्मिलनविधिः addLast() .

  1. public void addList(int data) {
  2.         ListNode node = new ListNode(data);
  3.         if (head == null) {
  4.             head = node;
  5.         }
  6.         ListNode cur = head;
  7.         while (cur.next != null) {
  8.             cur = cur.next;
  9.         }
  10.         cur.next = node;
  11.     }

3.adIndex () 1.1.

  1. public void addIndex(int index, int data) {
  2.         int len = size();
  3.         // 不合法
  4.         if (index < 0 || index > len) {
  5.             System.out.println("index不合法");
  6.             return;
  7.         }
  8.         // 空链表
  9.         if (index == 0) {
  10.             addFirst(data);
  11.             return;
  12.         }
  13.         // 尾部插入
  14.         if (index == len) {
  15.             addLast(data);
  16.             return;
  17.         }
  18.  
  19.         //中间位置插入
  20.         ListNode cur = head;
  21.         while (index - 1 != 0) {
  22.             cur = cur.next;
  23.             index--;
  24.         }
  25.         ListNode node = new ListNode(data);
  26.         node.next = cur.next;
  27.         cur.next = node;
  28.     }

४.युक्तम्() २.

  1. public boolean contains(int key) {
  2.         ListNode cur = head;
  3.         while (cur != null) {
  4.             if (cur.val == key) {
  5.                 return true;
  6.             }
  7.             cur = cur.next;
  8.         }
  9.         return false;
  10.     }

5.हटयतु() .

  1. public void remove(int key) {
  2.         if (head == null) {
  3.             return;
  4.         }
  5.         if (head.val == key) {
  6.             head = head.next;
  7.         }
  8.  
  9.         ListNode cur = findNodeOfKey(key);
  10.         if (cur == null) {
  11.             return;
  12.         }
  13.         ListNode del = cur.next;
  14.         cur.next = del.next;
  15.     }
  16.  
  17.     private ListNode findNodeOfKey(int key) {
  18.         ListNode cur = head;
  19.         while (cur.next != null) {
  20.             if (cur.next.val == key) {
  21.                 return cur;
  22.             }
  23.             cur = cur.next;
  24.         }
  25.         return null;
  26.     }

6.removeAllKey () 1.1.

  1. public void removeAllKey(int key) {
  2.         ListNode cur = head.next;
  3.         ListNode prev = head;
  4.         while (cur != null) {
  5.             if (cur.val == key) {
  6.                 prev.next = cur.next;
  7.             } else {
  8.                 prev = cur;
  9.             }
  10.             cur = cur.next;
  11.         }
  12.         if (head.val == key) {
  13.             head = head.next;
  14.         }
  15.     }

७.स्पष्टम्() २.

  1.  public void clear() {
  2.         ListNode cur = head;
  3.         while (cur != null) {
  4.             ListNode curNext = cur.next;
  5.             cur.next = null;
  6.             cur = curNext;
  7.         }
  8.         head = null;
  9.     }

८.आकारः() २.

  1. public int size() {
  2.         int count = 0;
  3.         ListNode cur = head;
  4.         while (cur != null) {
  5.             count++;
  6.             cur = cur.next;
  7.         }
  8.         return count;
  9.     }

9.प्रदर्शनम्() .

  1. public void display() {
  2.         ListNode cur = head;
  3.         while (cur != null) {
  4.             System.out.print(cur.val + " ");
  5.             cur = cur.next;
  6.         }
  7.     }

3.LinkedList इत्यस्य सिमुलेशन कार्यान्वयनम्

  1. / 2、无头双向链表实现
  2. public class MyLinkedList {
  3. //头插法
  4. public void addFirst(int data){ }
  5. //尾插法
  6. public void addLast(int data){}
  7. //任意位置插入,第一个数据节点为0号下标
  8. public void addIndex(int index,int data){}
  9. //查找是否包含关键字key是否在单链表当中
  10. public boolean contains(int key){}
  11. //删除第一次出现关键字为key的节点
  12. public void remove(int key){}
  13. //删除所有值为key的节点
  14. public void removeAllKey(int key){}
  15. //得到单链表的长度
  16. public int size(){}
  17. public void display(){}
  18. public void clear(){}
  19. }
  1. package DounlyLinkedList;
  2.  
  3. import java.util.LinkedList;
  4. import java.util.List;
  5.  
  6. public class MyDoublyLinkedList implements IList {
  7.  
  8.     static class ListNode {
  9.         public int val;
  10.         public ListNode next;
  11.         public ListNode prev;
  12.  
  13.         public ListNode(int val) {
  14.             this.val = val;
  15.         }
  16.     }
  17.  
  18.     public ListNode head;
  19.     public ListNode last;
  20.  
  21.  
  22.     @Override
  23.     public void addFist(int data) {
  24.         ListNode node = new ListNode(data);
  25.         if (head == null) {
  26.             head = node;
  27.             last = node;
  28.         } else
  29.             node.next = head;
  30.         head.prev = node;
  31.         head = node;
  32.     }
  33.  
  34.     @Override
  35.     public void addLast(int data) {
  36.         ListNode node = new ListNode(data);
  37.         if (head == null) {
  38.             head = node;
  39.             last = node;
  40.         }
  41.         last.next = node;
  42.         node.prev = last;
  43.         last = node;
  44.     }
  45.  
  46.     @Override
  47.     public void addIndex(int index, int data) {
  48.         int len = size();
  49.         if (index < 0 || index > len) {
  50.             System.out.println("index 不合法！");
  51.         }
  52.  
  53.         if (index == 0) {
  54.             addFist(data);
  55.             return;
  56.         }
  57.  
  58.         if (index == len) {
  59.             addLast(data);
  60.             return;
  61.         }
  62.         ListNode cur = findIndex(index);
  63.         ListNode node = new ListNode(data);
  64.         node.next = cur;
  65.         cur.prev.next = node;
  66.         node.prev = cur.prev;
  67.         cur.prev = node;
  68.     }
  69.  
  70.     private ListNode findIndex(int index) {
  71.         ListNode cur = head;
  72.         while (index != 0) {
  73.             cur = cur.next;
  74.             index--;
  75.         }
  76.         return cur;
  77.     }
  78.  
  79.  
  80.     @Override
  81.     public boolean contains(int key) {
  82.         ListNode cur = head;
  83.         int count = 0;
  84.         while (cur != null) {
  85.             if (cur.val == key) {
  86.                 return true;
  87.             }
  88.             cur = cur.next;
  89.         }
  90.         return false;
  91.     }
  92.  
  93.     @Override
  94.     public void remove(int key) {
  95.         ListNode cur = head;
  96.         while (cur != null) {
  97.             if (cur.val == key) {
  98.                 if (cur == head) {
  99.                     head = head.next;
  100.                     if (head != null) {
  101.                         head.prev = null;
  102.                     }
  103.                     head.prev = null;
  104.                 } else {
  105.                     cur.prev.next = cur.next;
  106.                     if (cur.next == null) {
  107.                         last = last.prev;
  108.                     } else {
  109.                         cur.next.next = cur.prev;
  110.                     }
  111.                 }
  112.                 return;
  113.             }
  114.             cur = cur.next;
  115.  
  116.         }
  117.     }
  118.  
  119.     @Override
  120.     public void removeAllKey(int key) {
  121.         ListNode cur = head;
  122.         while (cur != null) {
  123.             if (cur.val == key) {
  124.                 if (cur == head) {
  125.                     head = head.next;
  126.                     if (head != null) {
  127.                         head.prev = null;
  128.                     }
  129.                     head.prev = null;
  130.                 } else {
  131.                     cur.prev.next = cur.next;
  132.                     if (cur.next == null) {
  133.                         last = last.prev;
  134.                     } else {
  135.                         cur.next.next = cur.prev;
  136.                     }
  137.                 }
  138.             }
  139.             cur = cur.next;
  140.         }
  141.     }
  142.  
  143.     @Override
  144.     public int size() {
  145.         ListNode cur = head;
  146.         int count = 0;
  147.         while (cur != null) {
  148.             count++;
  149.             cur = cur.next;
  150.         }
  151.         return count;
  152.     }
  153.  
  154.     @Override
  155.     public void clear() {
  156.         ListNode cur = head;
  157.         while (cur != null) {
  158.             ListNode curNext = cur.next;
  159.             cur.next = null;
  160.             cur.prev = null;
  161.             cur = curNext;
  162.         }
  163.         head = null;
  164.         last = null;
  165.     }
  166.  
  167.     @Override
  168.     public void dispaly() {
  169.         ListNode cur = head;
  170.         while (cur != null) {
  171.             System.out.print(cur.val + " ");
  172.             cur = cur.next;
  173.         }
  174.         System.out.println();
  175.     }
  176. }
  177.  
  178.  
  179.  
  180.  
  181.  
  1. package DounlyLinkedList;
  2.  
  3. public interface IList {
  4.     void addFist(int data);
  5.  
  6.     void addLast(int data);
  7.  
  8.     void addIndex(int index, int data);
  9.  
  10.     boolean contains(int key);
  11.  
  12.     void remove(int key);
  13.  
  14.     void removeAllKey(int key);
  15.  
  16.     int size();
  17.  
  18.     void clear();
  19.  
  20.     void dispaly();
  21. }

4.LinkedList इत्यस्य उपयोगः

४.१ लिङ्क्ड्लिस् इति किम्

【दृष्टान्तः 】 २.

1. LinkedList List interface इत्यस्य कार्यान्वयनम् करोति

2. LinkedList इत्यस्य अन्तर्निहितस्तरः द्विगुणलिङ्कितसूचीं उपयुज्यते

3. LinkedList RandomAccess अन्तरफलकं कार्यान्वितं न करोति, अतः LinkedList यादृच्छिकप्रवेशस्य समर्थनं न करोति ।

4. LinkedList इत्यस्मिन् कस्मिन् अपि स्थाने तत्त्वानि सम्मिलितुं विलोपनं च तुल्यकालिकरूपेण कुशलं भवति, तथा च समयजटिलता O(1) भवति ।

5. LinkedList कस्मिन् अपि स्थाने सम्मिलनपरिदृश्यानां कृते अधिकं उपयुक्तम् अस्ति

४.२ LinkedList इत्यस्य उपयोगः

1. LinkedList इत्यस्य निर्माणम्

प्रक्रियाव्याख्याति
लिङ्क्ड्लिस्ट्() .नो-तर्कनिर्माणम्
public LinkedList (संग्रहअन्यसङ्ग्रहपात्रेभ्यः तत्त्वानां उपयोगेन List निर्मायताम्
  1. import java.util.LinkedList;
  2. import java.util.List;
  3.  
  4. public class Test {
  5.     public static void main(String[] args) {
  6.         List<Integer> list1 = new LinkedList<>();
  7.         List<String> list2 = new java.util.ArrayList<>();
  8.  
  9.         list2.add("javaSE");
  10.         list2.add("javaWeb");
  11.         list2.add("javaEE");
  12.  
  13.         List<String> list3 = new LinkedList<>(list2);
  14.         
  15.     }
  16. }
  17.  
  18.

2. LinkedList इत्यस्य अन्येषां सामान्यविधीनां परिचयः

प्रक्रियाव्याख्याति
बूलियन add(E e) 1.1.पुच्छ प्लग ङ
void add(int अनुक्रमणिका, ई तत्व)अनुक्रमणिकास्थाने e सम्मिलितं कुर्वन्तु
boolean addAll (संग्रह ग) 1.1.अन्ते c इत्यस्मिन् तत्त्वानि निवेशयन्तु
E remove(int index) २.अनुक्रमणिकास्थानतत्त्वं विलोपयन्तु
boolean remove(वस्तु ओ) २.प्रथमं o सम्मुखीकृतं विलोपयन्तु
E get(int index) ९.उपलिपि अनुक्रमणिका स्थितितत्त्वं प्राप्नुवन्तु
E set(int index, ई तत्व) 1.1.उपलिपि अनुक्रमणिकास्थानतत्त्वं तत्त्वे सेट् कुर्वन्तु
शून्य स्पष्ट() २.स्पष्टः
boolean contains(Object o) इति ।रेखीयसारणीयां o अस्ति वा इति निर्धारयतु
int indexOf(वस्तु ओ) .यत्र प्रथमः o स्थितः अस्ति तत्र अनुक्रमणिकां प्रत्यागच्छतु
int lastIndexOf (वस्तु o) .अन्तिमस्य o इत्यस्य उपलिपिं प्रत्यागच्छति
सूची subList(int fromIndex, int toIndex)सूचीयाः भागं अवरुद्धं कुर्वन्तु
  1. public static void main(String[] args) {
  2. LinkedList<Integer> list = new LinkedList<>();
  3. list.add(1); // add(elem): 表示尾插
  4. list.add(2);
  5. list.add(3);
  6. list.add(4);
  7. list.add(5);
  8. list.add(6);
  9. list.add(7);
  10. System.out.println(list.size());
  11. System.out.println(list);
  12. // 在起始位置插入0
  13. list.add(0, 0); // add(index, elem): 在index位置插入元素elem
  14. System.out.println(list);
  15. list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
  16. list.removeFirst(); // removeFirst(): 删除第一个元素
  17. list.removeLast(); // removeLast(): 删除最后元素
  18. list.remove(1); // remove(index): 删除index位置的元素
  19. System.out.println(list);
  20. // contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
  21. if(!list.contains(1)){
  22. list.add(0, 1);
  23. }
  24. list.add(1);
  25. System.out.println(list);
  26. System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
  27. System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
  28. int elem = list.get(0); // get(index): 获取指定位置元素
  29. list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
  30. System.out.println(list);
  31. // subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
  32. List<Integer> copy = list.subList(0, 3); 
  33. System.out.println(list);
  34. System.out.println(copy);
  35. list.clear(); // 将list中元素清空
  36. System.out.println(list.size());
  37. }

3. LinkedList इत्यस्य भ्रमणम्

  1. public static void main(String[] args) {
  2. LinkedList<Integer> list = new LinkedList<>();
  3. list.add(1); // add(elem): 表示尾插
  4. list.add(2);
  5. list.add(3);
  6. list.add(4);
  7. list.add(5);
  8. list.add(6);
  9. list.add(7);
  10. System.out.println(list.size());
  11. // foreach遍历
  12. for (int e:list) {
  13. System.out.print(e + " ");
  14. }
  15. System.out.println();
  16. // 使用迭代器遍历---正向遍历
  17. ListIterator<Integer> it = list.listIterator();
  18. while(it.hasNext()){
  19. System.out.print(it.next()+ " ");
  20. }
  21. System.out.println();
  22. // 使用反向迭代器---反向遍历
  23. ListIterator<Integer> rit = list.listIterator(list.size());
  24. while (rit.hasPrevious()){
  25. System.out.print(rit.previous() +" ");
  26. }
  27. System.out.println();
  28. }

5.ArrayList तथा ​​LinkedList इत्येतयोः मध्ये अन्तरम्

अंतरणArrayList इतिLinkedList इति
भण्डारणस्थानेभौतिकरूपेण निरन्तरता भवितुमर्हतितार्किकरूपेण निरन्तरता, न तु भौतिकरूपेण निरन्तरता इति अनिवार्यम्
यादृच्छिक अभिगमसमर्थन ओ(१) ९.समर्थितः नास्ति: O(N)
शिरः प्लगतत्त्वान् चालयितुं आवश्यकता, न्यूनदक्षता O(N)केवलं सन्दर्भस्य सूचकं परिवर्तयन्तु, समयजटिलता O(1) भवति ।
युज्यदा स्थानं अपर्याप्तं भवति तदा विस्तारस्य आवश्यकता भवतिन क्षमतायाः अवधारणा
अनुप्रयोग परिदृश्यतत्त्वानां कुशलं भण्डारणं + नित्यं प्रवेशःकस्मिन् अपि स्थाने बहुधा सम्मिलनम्, लोपः च

व्यक्तिगत प्रोफाइल

सः ३० वर्षाणाम् अधिकं कालात् प्रौद्योगिक्याः शोधकार्यं कर्तुं समर्पितः अस्ति, तथा च जावा, लिनक्स, जावास्क्रिप्ट्, php, css इत्यादिषु विविधभाषासु प्रवीणः अस्ति, मुक्तस्रोतक्षेत्रे सः बहु योगदानं कृतवान् अस्ति विकासक दस्तावेजीकरणस्थानकं भविष्ये सन्दर्भार्थं प्रौद्योगिकीविकासे केचन विषयाः साझां कर्तुं सर्वे तत् पश्यन्तु

मम सम्पर्कसूचना

मेल