자바 기초 정리: ArrayList vs. LinkedList

📍 Java List Collection

List는 Collection 인터페이스를 확장한 자료형으로 동일한 데이터의 중복 입력이 가능하며 순차적이고 다량의 데이터를 입력할 때 주로 사용합니다. 종류는 Vector, Arraylist, Linkedlist가 있습니다.

 

ArrayList	LinkedList
고정된 사이즈에 값을 넣을때 index로 관리  - 무작위 접근 가능 (random access) search는 빠르지만 삽입, 삭제 시 낭비되는 메모리가 많음	노드 간의 연결 형태로 연결    -추가 삭제시, 주소만 연결해주면 되기에 빠르고 용이함.    - sequential access  search 할때 자료 탐색 시간이 많이 소요된다.

 

 

✅ ArrayList

 - index로 객체를 관리한다.

 - 사이즈가 동적인 배열 

 - 처음 설정한 저장 용량 (capacity) 동적으로 늘릴수 있다. 

 - index 삭제하게 되면 하나씩 한칸씩 앞으로 이동한다. 

 - 객체가 추가되면 한칸씩 모두 뒤로 들어가게 된다. 

 - 인덱스 값 유지를 위해서 객체 전체의 위치가 이동한다. => 이동과 삭제가 어렵다. 

 

✅ LinkedList 

: 노드 간의 연결 (link)를 이용해서 리스트로 구현된 객체/

 - 인덱스를 가지고 있지 않기 때문에 탐색시 순차접근만 가능 (linear time)

 - 추가/삭제는 위치 정보의 수정만으로 가능하기에 성능이 좋음 

      > 추가 : 끝에 첨가 :O(1)  / 중간에 첨가 : O(N)

 - 어떠한 데이터도 가능하다. ex. char, string int

 - sorted, unsorted, duplicated, all unique 

 

😊 arraylist는 자료들이 하나의 연속적인 묶음으로 묶여 자료를 저장하지만

      linkedlist는 메모리 이곳저곳에 저장되어 있는 노드들을 접근하기 때문에 시간이 더 소모됩니다. 

작업	메소드	ArrayList	LinkedList
add at last index	add()	0(1)	O(1)
add at given index	add(index, value)	O(N)	O(1)
remove by index	remove(index)	O(N)	O(1)
remove by value	remove(value)	O(N)	O(1)
get by index	get(index)	O(1)	O(N)
search by index	indexOf(value)	O(N)	O(N)

 

 

📍 유사 문제 풀이 - LinkedList :

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

 

 

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode answer = new ListNode(0, head);
        
        ListNode pred = answer;
        
        while(head != null) {
            if(head.next != null && head.val == head.next.val) {
                while(head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                pred.next = head.next;
            } else {
                pred = pred.next;
            }
            head = head.next;
        }
        return answer.next;
    }
}

풀이 visualization :