LinkedList

자바의 정석[기초편]으로 공부한 내용을 정리한 글입니다.

 

LinkedList란?

• 데이터를 연결 구조(Linked Structure) 로 저장하는 자료구조입니다.
• 각 요소는 자기 데이터 + 다음 요소의 주소를 저장합니다.
• 이를 통해 데이터를 유연하게 추가하거나 삭제할 수 있습니다.

배열과의 차이점

1. 크기를 변경할 수 없다 (배열)
   배열은 미리 정해진 크기만큼만 저장할 수 있음 → 확장하려면 새 배열을 만들어 복사해야 함.
2. 삽입/삭제가 느림 (배열)
   중간에 삽입/삭제하면 뒤에 있는 요소들을 모두 이동시켜야 하므로 느림.

→ 이를 보완하기 위해 LinkedList가 등장!

 

배열과 LinkedList 비교

• 배열은 연속된 공간(예: 0x100 ~ 0x10C 등)에 데이터를 저장
  arr[0] = 1, arr[1] = 2, ... 이런 식으로 주소 계산으로 접근 가능
• LinkedList는 각 노드가 다음 노드를 가리키는 포인터를 가지고 있음
   
   
   

class Node {
    Node next;     // 다음 노드 주소 저장
    Object obj;    // 실제 데이터 저장
}

linkedList = Node(1) -> Node(2) -> Node(3) -> Node(4) -> null

 

LinkedList의 추가와 삭제

요소 삭제

• 중간 요소(예: 3번 노드)를 삭제하고 싶으면?
  • 이전 노드가 다음 노드를 그 다음 노드로 바꿔치기하면 됩니다.
  • 즉, Node(2).next → Node(4)로 연결 변경

요소 추가

• 2와 3 사이에 2.5라는 요소를 추가하려면?
  1. 새로운 노드를 생성: newNode(2.5)
  2. newNode.next = Node(3)
  3. Node(2).next = newNode

이처럼 링크만 조작하면 되기 때문에, 삽입/삭제가 빠름

 

ArrayList와 LinkedList의 비교

ArrayList의 구조

• 연속된 메모리 공간에 데이터 저장
• 접근 방식

arr[n]의 주소 = arr의 시작 주소 + n * 데이터 크기

예시:
arr = new Object[5]일 때

• 참조형 변수의 크기가 4바이트면
• arr[2]의 주소는 0x100 + 2 * 4 = 0x108

👉 그래서 ArrayList는 인덱스로 접근이 매우 빠름

 

성능 비교

컬렉션	읽기(접근시간)	추가/삭제	비고
ArrayList	빠르다	느리다	순차적 추가/삭제는 빠름, 비효율적 메모리
LinkedList	느리다	빠르다	데이터 많을수록 접근성 떨어짐

 

 

결론

• 읽기(접근) 중심이면 → ArrayList 추천
• 자주 삽입/삭제가 일어난다면 → LinkedList가 더 효율적