Java 배열리스트와 연결리스트

앞서 배열리스트와 연결리스트를 직접 구현하였다.

빅오 비교 표

• 배열리스트는 인덱스를 통한 추가 및 삭제에는 (1) 으로 빠르다.
• 연결 리스트는 인덱스를 통한 추가 및 삭제에는 (n) 으로 느리다. 찾은 다음 참조 값만 변경하므로 O(1) 속도이다.
• 데이터를 인덱스로 처음 위치 접근해 추가할 경우
  • 배열리스트는 데이터를 이동시켜야하므로 O(n)이다.
  • 연결리스트는 참조 값만 변경하고 데이터를 입력하므로 O(1)이다.
• 데이터를 마지막 위치로 접근해 추가할 경우
  • 배열리스트는 마지막 위치를 바로 찾는다. O(1)
  • 연결리스트는 마지막까지 순회하며 노드를 찾아야한다. 마지막 노드에는 O(1) 속도가 걸린다.

배열리스트과 연결리스트 각각의 사용처

데이터를 조회할 일이 있으며 뒷 부분에 데이터를 추가한다면 배열 리스트가 좋은 성능을 나타낸다.
앞쪽 데이터를 추가나 삭제할 일이 있다면 연결 리스트 사용이 더 좋은 성능을 제공한다.

연결리스트 종류

단일 연결 리스트

• 이전에 직접 구현한 연결 리스트는 단일 연결 리스트이다.
• 노드를 앞 뒤로 모두 연결해 이중 연결 리스트 사용으로 성능을 개선할 수 있다.
• 자바가 제공하는 연결 리스트는 이중 연결리스트이다.
  • 마지막 노드를 참조하는 변수를 가지고 있으므로, 뒤에 추가나 삭제에 O(1) 성능을 자랑한다.

이중 연결 리스트 예시 - Node

public class Node {
    Object item;
    Node next;
    Node prev;
}

이중 연결 리스트 예시 - LinkedList (last 필드 추가)

public class LinkedList {
    private Node first;
    private Node last;
    private int size = 0;
}