ArrayList LinkedList

ArrayList와 LinkedList는 데이터의 저장 방식과 접근 방식에 있다.

 

 

ArrayList:

내부적으로 배열을 사용하여 데이터를 저장하고 요소를 추가하거나 삭제할 때 배열의 크기를 조정, 이동해야 할 수 있으므로 연산의 속도가 느릴 수 있지만 임의의 위치에 있는 요소에 빠르게 접근할 수 있다.

 

 

LinkedList: 노드의 연결 리스트를 사용하여 데이터를 저장하며 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 요소를 추가하거나 삭제할 때 다음 노드의 포인터를 조정하여 삽입 또는 삭제를 수행한다. 중간에 요소를 추가하거나 삭제할 때 배열을 이동할 필요가 없으므로 연산의 속도가 빠르지만 인덱스를 통한 빠른 접근이 불가능하며, 원하는 위치에 도달하기 위해 첫 번째 노드부터 차례대로 탐색해야 한다.

 

 

 

 

단일 연결 리스트 구현 

#Node 클래스
class Node:
    def __init__(self,data):
        self.data=data #노드가 저장하는 데이터
        self.next=None #다음 노드를 가리키는 포인터


#node 클래스는 데이터를 저장하는 data 속성과 다음 노드를 가리키는 next 포인터로 구성된다
#초기화 메서드에서 데이터를 입력받아 self.data에 할당한다.

#LinkedList 클래스
#단일 연결 리스트를 구현한다
class LinkedList:
    def __init__(self):
        self.head=None #연결 리스트의 시작 노드, 초기값은 None
#self.head는 연결 리스트의 첫 번째 노드를 가리키는 포인터이다.
    def append(self,data):
        new_node=Node(data) #새로운데이터를 가진 노드 생성
        # 데이터를 매개변수로 받아 새로운 노드를 생성하고 연결 리스트 끝에 추가한다.

        if not self.head:
            self.head=new_node #연결 리스트가 비어있다면 새 노드를 head 로 설정
            return
#만약 연결 리스트가 비었다면 새 노드를 첫 노드로 설정한다.
    
        
        last_node = self.head
        while last_node.next:
            last_node=last_node.next
        last_node.next=new_node #마지막 노드의 다음을 새 노드로 설정
#그렇지 않으면 마지막 노드를 찾아가서 뒤에 새로운 노드를 추가한다.
    
    def print_list(self):
        current_node=self.head
        while current_node:
            print(current_node.data, end=" ")  # 현재 노드의 데이터 출력
            current_node = current_node.next  # 다음 노드로 이동
        print()
#연결 리스트의 모든 노드의 데이터를 순서대로 출력
#current_node.next를 통해 마지막 노드까지 이동하며 출력



# 빈 LinkedList 생성
linked_list = LinkedList()

# 요소 추가
linked_list.append(10)
linked_list.append(20)
linked_list.append(30)
linked_list.append(50)
# 모든 요소 출력
linked_list.print_list()

 

 

 

 

 

 

 

 

 

 

성능

package study.dataStructure;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ArrayListLinkedListTest {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>(2000000);
        //초기 용량 리스트 생성 초기 버퍼 크기를 의미한다.
        LinkedList<String> linkedList = new LinkedList<>();

        System.out.println("====== 순차적으로 추가하기 ======");
        long addFArrayListTime = addF(arrayList);
        long addFLinkedListTime = addF(linkedList);
        System.out.println("ArrayList: " + addFArrayListTime + " ms");
        System.out.println("LinkedList: " + addFLinkedListTime + " ms");
        System.out.println("LinkedList / ArrayList: " + ((double) addFLinkedListTime / addFArrayListTime));

        System.out.println("\n====== 중간에 추가하기 ======");
        long addMArrayListTime = addM(arrayList);
        long addMLinkedListTime = addM(linkedList);
        System.out.println("ArrayList: " + addMArrayListTime + " ms");
        System.out.println("LinkedList: " + addMLinkedListTime + " ms");
        System.out.println("LinkedList / ArrayList: " + ((double) addMLinkedListTime / addMArrayListTime));

        System.out.println("\n====== 중간에 삭제하기 ======");
        long removeMArrayListTime = removeM(arrayList);
        long removeMLinkedListTime = removeM(linkedList);
        System.out.println("ArrayList: " + removeMArrayListTime + " ms");
        System.out.println("LinkedList: " + removeMLinkedListTime + " ms");
        System.out.println("LinkedList / ArrayList: " + ((double) removeMLinkedListTime / removeMArrayListTime));

        System.out.println("\n====== 순차적으로 삭제하기 ======");
        long removeFArrayListTime = removeF(arrayList);
        long removeFLinkedListTime = removeF(linkedList);
        System.out.println("ArrayList: " + removeFArrayListTime + " ms");
        System.out.println("LinkedList: " + removeFLinkedListTime + " ms");
        System.out.println("LinkedList / ArrayList: " + ((double) removeFLinkedListTime / removeFArrayListTime));
    }
//0부터 999999까지 순차적으로 리스트에 추가한다
    public static long addF(List<String> list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list.add(String.valueOf(i));
        }
        long end = System.currentTimeMillis();
        return end - start;
        
    }
//리스트 중간 500인덱스에 x문자를 추가하는 연산
    public static long addM(List<String> list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            list.add(500, "X");
        }
        long end = System.currentTimeMillis();
        return end - start;
    }
//리스트 마지막에서 처음까지 역순으로 요소 삭제
    public static long removeF(List<String> list) {
        long start = System.currentTimeMillis();
        for (int i = list.size() - 1; i >= 0; i--) {
            list.remove(i);
        }
        long end = System.currentTimeMillis();
        return end - start;
    }
//처음부터 끝까지 요소 삭제
    public static long removeM(List<String> list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            list.remove(i);
        }
        long end = System.currentTimeMillis();
        return end - start;
    }
}

====== 순차적으로 추가하기 ======
ArrayList: 23 ms
LinkedList: 32 ms
LinkedList / ArrayList: 1.391304347826087

====== 중간에 추가하기 ======
ArrayList: 5860 ms
LinkedList: 23 ms
LinkedList / ArrayList: 0.003926701570680628

====== 중간에 삭제하기 ======
ArrayList: 14 ms
LinkedList: 57 ms
LinkedList / ArrayList: 4.071428571428571

====== 순차적으로 삭제하기 ======
ArrayList: 9 ms
LinkedList: 15770 ms
LinkedList / ArrayList: 1752.2222222222222

 

1.  순차적으로 추가 
   - ArrayList: 23 ms
   - LinkedList: 32 ms
   - LinkedList / ArrayList: 1.391304347826087
   - 순차적으로 요소를 추가할 때, ArrayList가 LinkedList보다 약간 더 빠르게 작동하는데 LinkedList가 ArrayList보다 조금 느린 이유는 매번 새로운 노드를 생성하고 연결해야 하기 때문이다. 

 

 

2. 중간에 추가
   - ArrayList: 5860 ms
   - LinkedList: 23 ms
   - LinkedList / ArrayList: 0.003926701570680628
   - 중간에 요소를 추가할 때, LinkedList가 훨씬 더 빠르다. LinkedList가 특정 인덱스에 새로운 요소를 추가할 때, 해당 인덱스를 찾아가는 과정만 거치면 되지만, ArrayList는 해당 인덱스 이후의 모든 요소를 뒤로 이동시켜야 하기 때문이다. 

3. 중간에 삭제하기
   - ArrayList: 14 ms
   - LinkedList: 57 ms
   - LinkedList / ArrayList: 4.071428571428571
   - 중간에 요소를 삭제할 때, ArrayList가 훨씬 더 빠르다. ArrayList에서는 해당 인덱스의 요소를 삭제한 후, 그 이후의 요소들을 앞으로 이동시키면 되지만, LinkedList에서는 해당 노드를 찾아가는 과정과 연결을 끊는 과정이 필요하기 때문이다. 

4. 순차적으로 삭제하기:
   - ArrayList: 9 ms
   - LinkedList: 15770 ms
   - LinkedList / ArrayList: 1752.2222222222222
   - 순차적으로 요소를 삭제할 때, ArrayList가 훨씬 더 빠른다. ArrayList에서는 요소를 한 번에 삭제할 수 있지만, LinkedList에서는 각 요소를 찾아가서 연결을 끊어야 하기 때문에 시간이 오래 걸린다.  

 

  데이터를 순차적으로 추가하거나 삭제하는 경우에는 ArrayList가 더 효율적이며, 중간에 요소를 추가 또는 삭제하는 경우에는 LinkedList가 더 효율적이다.