Java의 연결 목록 데이터 구조

다른 목적을 위해 다른 데이터 구조가 생성됩니다. ArrayList 에 대해 알고 계실 수도 있습니다 (아직도 모르신다면 먼저 관련 내용을 읽어 보시기 바랍니다). 이 기사에서는 LinkedList 에 대해 알아보고 이 컬렉션이 무엇에 유용한지 알아봅니다. LinkedList Java 8(또는 이후 버전의 언어) 클래스 코드 소스(오라클 웹 사이트 또는 IDE에서 IDEA의 경우: 클래스 이름에 crtl+B)를 보면 다음 선언이 표시됩니다.

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

현재 코드에서 가장 중요한 정보는 LinkedList가 List 및 Deque 인터페이스를 구현한다는 사실입니다 . List 인터페이스는 항목 추가 순서를 유지하고 인덱스별로 항목에 액세스할 수 있도록 합니다. "일반" Queue는 끝에 요소를 추가하고 처음부터 추출하는 것을 지원합니다. Deque는 양방향 대기열이며 양쪽에서 요소 추가 및 제거를 지원합니다. 스택과 큐의 조합으로 생각할 수 있습니다. 따라서 LinkedList는 이 두 가지를 구현한 것으로 null을 포함한 모든 개체로 구성된 양방향 대기열을 만들 수 있습니다. LinkedList요소 모음입니다. 클래스의 코드 소스에서 볼 수 있습니다. 이번에는 필드에 주의를 기울이십시오.

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

일반적으로 Node 라고 하는 모든 요소에는 객체와 인접한 두 객체(이전 객체와 다음 객체)에 대한 참조가 포함되어 있습니다. 따라서 메모리 사용 측면에서 그다지 효과적이지 않습니다. LinkedList는 실제로 양방향 구조 이므로 양쪽에서 요소를 쉽게 추가하거나 제거할 수 있습니다.

LinkedList 생성자

코드 소스로 돌아가서 LinkedList 에 두 개의 생성자가 있음을 알 수 있습니다.

• 매개변수가 없는 LinkedList()는 빈 목록을 구성하는 데 사용됩니다.
• >LinkedList(Collection<? extends E> c)는 지정된 컬렉션의 요소를 포함하는 목록을 생성하기 위한 것으로 컬렉션의 반복자에 의해 반환됩니다.

LinkedList 선언

실제로 연결된 목록(Java 또는 다른 언어)은 일련의 노드로 구성됩니다. 모든 노드는 생성 시 정의된 유형의 개체를 저장하도록 설계되었습니다. 따라서 LinkedList를 생성하기 위해 Java 코드는 다음과 같습니다.

LinkedList<Integer> myList = new LinkedList<>();

이웃에 대한 일련의 정수와 링크를 유지하는 개체가 있습니다. 그러나 현재 비어 있습니다.

LinkedList 주요 작업

늘 그렇듯이 Collections의 경우 요소를 LinkedList 에 넣고 (끝이나 중간에) 거기에서 제거한 다음 인덱스로 요소를 가져올 수 있습니다. 여기 있습니다:

• add(E element) 이 목록의 끝에 지정된 요소를 추가합니다.
• add(int index, E element) 지정된 위치 index 에 요소를 삽입합니다 .
• get(int index) 이 목록의 지정된 위치에 있는 요소를 반환합니다.
• remove(int index) 인덱스 위치에 있는 요소를 제거합니다.
• remove(Object o) ?의 첫 번째 항목을 제거합니다. o 이 목록에 있는 경우 이 목록의 요소.
• remove() 목록의 첫 번째 요소를 검색하고 제거합니다.

요소를 추가 및 제거하는 Java의 연결 목록 구현. 예

연습을 통해 이러한 작업을 시도해 봅시다. 첫째, Java LinkedList 구현: 문자열의 LinkedList를 생성하고 거기에 3개의 요소를 추가합니다. 그런 다음 하나를 제거한 다음 중간에 하나를 추가하십시오.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

이 프로그램을 실행한 결과:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

LinkedList 는 Collection 프레임워크 의 일부이며 , Iterator를 사용하여 요소를 제거할 수 있으며 목록에 대한 특수 반복기인 ListIterator 도 사용할 수 있습니다 . 더욱이 반복자를 사용한 작업은 LinkedList 클래스의 주요 이점인 삽입/삭제 작업의 우수한 성능을 제공합니다. Iterator를 사용하면 일정한 시간을 얻을 수 있습니다. 이 문서의 뒷부분에서 ArrayList 와 LinkedList+Iterator를 비교하는 코드 예제를 작성합니다.

• Iterator.remove()는 이 반복자가 반환한 마지막 요소를 제거합니다.
• ListIterator.add(E element) 목록에 요소를 삽입합니다.

Java LinkedList 예제: Iterator 작동 방식

여기 우리는 Iterator를 통해 추가 및 삭제를 시도하는 작은 Java LinkedList 예제 코드가 있습니다.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

이 프로그램을 실행한 결과:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

추가 Java LinkedList 작업:

• addFirst() , addLast() 목록의 시작/끝에 요소 추가
• clear()는 목록에서 모든 요소를 ​​제거합니다.
• contains(Object o)는 목록에 o 요소가 포함되어 있으면 true를 반환합니다.
• indexOf(Object o)는 o 요소가 처음 나타나는 인덱스를 반환하거나 목록에 없으면 -1을 반환합니다.
• set(int index, E element) 인덱스 위치에 있는 요소를 해당 요소로 바꿉니다.
• size()는 목록에 있는 요소의 수량을 반환합니다.
• toArray()는 처음부터 마지막 ​​요소까지 목록의 모든 요소를 ​​포함하는 배열을 반환합니다.

BTW는 크기가 두 개인 대기열이며 Java의 LinkedList 에는 스택 관련 작업이 있습니다.

• 스택에서 요소를 팝하는 pop() (목록으로 표시됨)
• 스택에 요소를 푸시하는 push(E e) (이 목록으로 표시됨)

LinkedList를 뒤집는 방법: 예

다음은 인기가 있지만 초보자에게 쉬운 작업인 작은 예입니다. 우리는 LinkedList를 가지고 있고 그것을 되돌려야 합니다. 가장 쉬운 알고리즘은 LinkedList를 역순으로 살펴보고 모든 요소를 ​​새 요소에 넣는 것입니다 . 하지만 더 나은 방법을 찾을 수 있을까요? 다음은 역방향 연결 목록 자바 프로그램의 코드입니다.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

결과:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList vs ArrayList: 첫 번째 것을 사용할 때

LinkedList 와 ArrayList 는 모두 List 인터페이스 의 구현입니다 . LinkedList는 이중 연결 목록으로 구현합니다. ArrayList는 동적으로 크기를 조정하는 배열을 사용하여 이를 구현합니다. 이미 알고 있듯이 LinkedList 의 모든 노드 에는 객체와 이웃에 대한 두 개의 참조가 포함되어 있습니다. 이는 Java LinkedList 의 경우 요소 간 참조를 저장하기 위한 추가 메모리 비용을 의미합니다 . ArrayList는 동적으로 크기를 조정하는 배열로 이를 구현합니다. 일부 LinkedList 및 ArrayList 작업은 동일하게 보이지만 다른 방식으로 작동합니다. ArrayList 에서경우 LinkedList 에서 참조를 사용하여 내부 배열을 조작합니다 . ArrayList 는 가장 널리 사용되는 List 구현입니다. 이러한 작업은 일정한 시간에 수행되므로 인덱스 액세스가 우선 순위인 경우 반드시 ArrayList를 사용해야 합니다 . 평균적으로 목록 끝에 추가하는 것도 일정한 시간에 수행됩니다. 더욱이 ArrayList에는 여러 요소를 저장하기 위한 추가 비용이 없습니다. 목록의 끝에서 완료되지 않은 경우 삽입 및 제거 작업 속도를 Cons로 간주할 수 있습니다. LinkedList어떤 면에서 삽입 및 삭제 작업 성능의 경우에 더 유용합니다. 반복자를 사용하는 경우 일정한 시간에 발생합니다. 인덱스에 의한 액세스 작업은 끝의 시작 부분(둘 중 더 가까운 쪽)에서 원하는 요소까지 검색하여 수행됩니다. 그러나 요소 간 참조를 저장하기 위한 추가 비용을 잊지 마십시오. 여기에서는 알고리즘 런타임을 사용하는 표준 LinkedList 및 ArrayList 작업이 있습니다. N은 이미 목록에 있는 항목의 수를 나타냅니다. O(N)은 최악의 경우 예를 들어 새 요소를 목록에 삽입하기 위해 필요한 위치를 찾을 때까지 전체 목록을 "보행"해야 함을 의미합니다. 오(1)작업이 항목 수에 관계없이 일정한 시간에 발생함을 의미합니다.

LinkedList 시간 복잡도

ArrayList 시간 복잡도

LinkedList 사용 시기: 예

확실히 ArrayList는 가장 널리 사용되는 List 구현입니다. 그러나 추가/제거 작업이 너무 자주 필요한 상황을 만날 수 있습니다. 이 경우 Iterator와 함께 LinkedList가 모두 도움이 될 수 있습니다. 다음은 예입니다. 긴 목록이 있고 이 목록에서 모든 요소를 ​​삭제해야 합니다. ArrayList 및 LinkedList + Iterator 로 이 작업을 수행해 보겠습니다 . 우리는 모든 작업의 ​​시간을 비교하고 콘솔에 출력합니다. 코드는 다음과 같습니다.

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

ArrayList에 대한 결과:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

LinkedList에 대한 결과:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

이 경우에서 볼 수 있듯이 LinkedList가 훨씬 더 효과적입니다. 솔직해지자. 실제 소프트웨어 개발에서 LinkedList 사용은 일종의 드문 이벤트입니다. 그럼에도 불구하고 전문가는 이러한 데이터 구조의 존재와 이점에 대해 알아야 합니다. 실제 코드에서 LinkedList가 드문 손님이라면 Java Junior 인터뷰에서 매우 인기가 있습니다. 그럼에도 불구하고 Joshua Bloch가 LinkedList 에 대해 쓴 내용은 다음과 같습니다 .

애드온: 단일 연결 목록 Java

Java의 고전적인 Collection 에는 Singly Linked List가 없습니다 . Singly Linked List는 모든 노드가 객체와 다음 노드에 대한 참조를 포함하지만 이전 노드에 대한 참조는 포함하지 않는 구조입니다. Java LinkedList 는 2개로 연결되어 있지만 Singly ,code>Linked List와 같은 고유한 데이터 구조를 만드는 데 방해가 되는 사람은 아무도 없습니다. 다음은 이러한 작업을 해결하기 위한 몇 가지 단계입니다.

1. data 및 next라는 두 가지 특성을 사용하여 Node 클래스를 만듭니다 . 다음은 다음 노드에 대한 참조입니다.
2. 머리와 꼬리라는 두 가지 특성을 사용하여 FirstLast 클래스를 만듭니다 .
3. 목록에 새 노드를 추가하는 add() 메서드를 만듭니다 . 먼저 목록이 비어 있는지 확인하십시오( head == null ). 그렇다면 head와 tail은 새 노드를 참조합니다. 목록이 비어 있지 않으면 끝에 새 노드가 추가되므로 꼬리의 다음 속성은 추가된 노드를 참조하고 새 노드가 목록의 꼬리가 됩니다.

그건 그렇고 연습으로 자신의 LinkedList를 만들려고 할 수도 있습니다 . 학습에 행운을 빕니다.