ArrayList와 LinkedList는 Java에서 제공하는 Collection으로 List 인터페이스를 상속한다.
ArrayList : Java 1.2 에서 추가. 동기화가 제공되지 않음. 데이터의 검색에 유리하며 추가, 삭제에는 성능을 고려해야 한다.
LinkedList :Java 1.2 에서 추가. ArrayList 에 비해 데이터의 추가, 삭제에 유리하며 데이터 검색 시에는 성능을 고려해야 한다.
1. 공간적 제약
ArrayList
결국 배열이므로 길이가 고정돼 있다. 배열에 새로운 요소를 추가할 때, 배열의 용량이 이미 가득 차있다면 새로운 배열을 생성해주어야 한다.
이 때, 새로운 위치에 배열이 생성되니 모든 요소를 복사해서 새로 만드는 것이다. 기존에 값이 있었던 메모리공간은 안쓰게 된다. 그래서 몌모리 resource가 많이 드는 것이다.
그 때 메모리에 여유공간이 없는 경우 에러가 발생할 수도 있다.
새로운 요소를 추가할때,
여유공간이 없을 땐, O(n)
여유공간이 있을 땐, O(1)이다.
LinkedList
데이터를 저장하는 하나의 Node는 연결된 이전 Node, 다음 Node에 대한 '참조'만 가지고 있다. 따라서 ArrayList처럼 데이터 추가/삭제시 데이터의 복사가 없어 공간적 제약이 거의 없다.
반면 데이터의 검색시에는 처음부터 노드를 순회해야 하기 때문에 성능상 불리하다.
새로운 요소를 추가할때,
항상 O(1)이다.
2. 접근
- 임의 접근(Random Access) : 어떤 요소에 바로 접근하는 것.
- 순차 접근(Sequential Access) : 어떤 요소에 접근할 때, 차례차례 접근하는 것.
ArrayList :임의 접근, 바로 접근이 가능하다는 것은 곧 O(1)을 의미한다.
LinkedList : 순차 접근만 가능, O(n)이 걸리게 됩니다.
3. 검색
ArrayList
각 데이터의 index를 가지고 있으므로 바로 검색할 수 있어 빠르다. get(int index) 를 통해 O(1)의 시간 복잡도를 가진다.
LinkedList
제일 앞에 있는 데이터부터 차례대로 모든 요소를 찾아가야 하므로 최악의 경우에는 O(N)의 시간 복잡도를 가진다.
4. 데이터 삽입 & 삭제
데이터를 삽입, 삭제할 때 ,
ArrayList
삭제시 빈공간은 쉬프트해서 옮겨야 한다.
임시 배열을 만든 후 추가할 위치 앞까지는 그대로 복사하고 데이터를 추가한 다음 나머지 데이터가 추가된다.
최악의 경우 O(N)의 성능을 내게 된다.
LinkedList
데이터의 뒤쪽 데이터를 바라보는 주솟값만 바꿔주면 된다.
이전 노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문이다.
삽입, 삭제가 일어날 때 O(1)의 시작 복잡도를 가진다.
5. 소스
LinkedList
public class ListNode {
int data; // Data Field
ListNode next; // Link Field, 뒤쪽 포인터(다음 노드 참조)
public ListNode() {
}
/**
* 데이터를 저장하는 ListNode 생성자
*/
public ListNode(int data) {
this.data = data;
this.next = null;
}
/**
* 데이터 추가
*/
public ListNode add(ListNode head, ListNode nodeToAdd, int position) {
ListNode node = head;
// 맨 앞에 삽입할 경우
if (position == 0) {
// head에 data가 없는 경우, 노드가 0개인 경우
if (head == null) return nodeToAdd;
// head에 data가 있는 경우, 노드가 1개 이상인 경우
ListNode insertNode = nodeToAdd;
insertNode.next = head;
head = insertNode;
return head;
}
// 맨 압에 삽입하지 않는 경우
// position 바로 앞까지 순차 탐색
for (int i = 0; i < position - 1; i++) { // or While(node.next != null)
node = node.next;
}
nodeToAdd.next = node.next;
node.next = nodeToAdd;
return head;
}
/**
* 데이터 삭제
*/
public ListNode remove(ListNode head, int positionToRemove) {
ListNode node = head;
// 삭제 노드가 헤드일 경우
if (positionToRemove == 0) {
// 1번 인덱스 노드를 헤드로 지정
head = head.next;
} else {
// 순차 탐색
for (int i = 0; i < positionToRemove - 1; i++) {
node = node.next;
}
ListNode removeNode = node.next;
node.next = removeNode.next;
}
return head;
}
/**
* 데이터 포함 여부 확인
*/
public boolean contains(ListNode head, ListNode nodeToCheck) {
// 노드가 하나라도 있다면
while (head != null) {
// 찾는 데이터가 head면 true 리턴
if (head.data == nodeToCheck.data) return true;
// checkNode 찾을 때까지 순차 탐색
head = head.next;
}
// 탐색 후 없으면 false 반환
return false;
}
@Override
public String toString() {
return "ListNode{" +
"data=" + data +
", next=" + next +
'}';
}
/**
* ListNode 테스트
*/
public static void main(String[] args) {
// 초기 head data : 1 삽입
ListNode node = new ListNode(1);
ListNode head = node;
/**
* head : 1
* 2~4 노드 순서대로 삽입 (FIFO)
*/
System.out.println("-----순서대로 삽입------");
for(int i=1; i<4; i++){
head = node.add(head, new ListNode(i+1),i);
System.out.println(head.toString());
}
System.out.println();
/**
* 노드 중간 삽입
* head-1-2-3-4-Null
* >> head-1-2-10-3-4-Null
*/
System.out.println("-----중간 삽입------");
head = node.add(head, new ListNode(10),2);
System.out.println(head.toString());
System.out.println();
/**
* 노드 삭제
*/
System.out.println("-----노드 삭제------");
// head 삭제
// head-2-10-3-4-Null
head = node.remove(head,0);
System.out.println(head.toString());
// index :2 삭제
// head-2-10-4-Null
head = node.remove(head,2);
System.out.println(head.toString());
System.out.println();
/**
* 노드 포함여부 확인
* head-2-10-4-Null
*/
System.out.println("1 포함여부 :"+ node.contains(head, new ListNode(1))); // false
System.out.println("10 포함여부 :" + node.contains(head, new ListNode(10))); // true
}
}결과
- 연결리스트 판단
head == null // 노드 0개, 연결리스트가 비어 있는 것!head.next == null // 노드 1개
head.next.next == null // 노드 2개node.next == null // node가 가리키는 노드가 꼬리인지 체크!참고
