기술나눔

LinkedList와 연결리스트

2024-07-12

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

1. ArrayList의 결함

ArrayList의 임의 위치에 요소를 삽입하거나 삭제하려면 이후의 요소 전체를 앞으로 또는 뒤로 이동해야 하며 시간 복잡도가 O(n)이므로 효율성이 상대적으로 낮습니다. 위치. 따라서 연결된 목록 구조인 LinkedList가 Java 컬렉션에 도입되었습니다.

2. 연결리스트

2.1 연결리스트의 개념과 구조

연결리스트(linked list)는 물리적으로 비연속적인 저장 구조로, 연결리스트의 참조 링크 순서에 따라 데이터 요소의 논리적 순서가 결정된다.

2.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.인덱스 추가()

  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.     }

4.포함()

  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.모든키제거()

  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.     }

7.지우기()

  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.     }

8.크기()

  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의 활용

4.1 LinkedLis란 무엇입니까?

【그림을 그리다】

1. LinkedList는 List 인터페이스를 구현합니다.

2. LinkedList의 기본 레이어는 이중 연결 목록을 사용합니다.

3. LinkedList는 RandomAccess 인터페이스를 구현하지 않으므로 LinkedList는 임의 액세스를 지원하지 않습니다.

4. LinkedList의 임의 위치에 요소를 삽입하고 삭제하는 것은 상대적으로 효율적이며 시간 복잡도는 O(1)입니다.

5. LinkedList는 모든 위치의 삽입 시나리오에 더 적합합니다.

4.2 LinkedList의 사용

1. LinkedList 구축

방법설명하다
연결 리스트()무인수 건설
공개 LinkedList(컬렉션다른 컬렉션 컨테이너의 요소를 사용하여 목록 구성
  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의 다른 일반적인 방법 소개

방법설명하다
불리언 추가(E e)테일 플러그 e
void add(int 인덱스, E 요소)인덱스 위치에 e 삽입
boolean addAll(컬렉션 c)c의 끝에 요소 삽입
E 제거(int index)인덱스 위치 요소 삭제
boolean remove(Object o)처음 발생한 o 삭제
E get(int 인덱스)아래 첨자 색인 위치 요소를 가져옵니다.
E set(int 인덱스, E 요소)아래 첨자 색인 위치 요소를 요소로 설정
무효 지우기()분명한
boolean 포함(Object o)o가 선형 테이블에 있는지 확인
int indexOf(객체 o)첫 번째 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의 차이점

차이점배열 목록연결 리스트
저장 공간에물리적으로 연속적이어야 함논리적으로 연속적이지만 반드시 물리적으로 연속적일 필요는 없음
무작위 액세스지원 O(1)지원되지 않음: O(N)
헤드 플러그요소 이동 필요, 효율성 낮음 O(N)참조 포인터를 수정하면 시간 복잡도는 O(1)입니다.
끼워 넣다공간이 부족할 경우 확장이 필요함용량 개념이 없음
애플리케이션 시나리오효율적인 요소 저장 + 빈번한 액세스어느 위치에서나 자주 삽입 및 삭제됨

개인 프로필

그는 30년 이상 기술 연구에 전념해 왔으며, java, linux, javascript, php, css 등 다양한 언어에 능숙하며, 오픈 소스 분야에 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편