list.remove(); // 첫 번째 값 제거
list.remove(3); // 3번째 값 제거
list.removeFirst(); // 첫번째 값 제거
list.lastFirst(); // 마지막 값 제거
list.clear(); // 모든 값 제거LinkedList
LinkedList(연결리스트)는 데이터가 저장되어 있는 노드(Node) 객체들을 참조 체인으로 엮어 놓은 자료구조다.
LinkedList 객체 안쪽에는 노드들이 참조 체인으로 연결되어 있다. 각 노드들은 다음에 위치한 노드들의 참조를 들고 있다. 사용자는 LinkedList의 첫 번째 노드부터 따라가면서 원하는 데이터를 조회하게 된다.
ArrayList와 다르게 중간에 데이터가 추가되거나 중간에 있는 데이터가 삭제되어도 앞으로 땡기거나 뒤로 미는 동작이 없다. 단지 추가되거나 삭제될 노드 위치의 바로 앞쪽에 있는 노드의 참조를 변경하기만하면 된다. 즉, LinkedList로의 데이터 추가나 삭제 동작이 용이하다.
반면 특정 데이터를 인덱스 값을 통해 바로 따라갈 수 있는 방법이 없다는 단점은 있다. LinkedList의 100번째 노드를 확인하기 위해서는 첫 번째 노드부터 100번째 노드까지 참조를 따라서 이동해야 확인할 수 있다. 이 때문에 특정 노드까지 따라가는 탐색 성능이 떨어진다.
LinkedList 사용법
LinkedList 선언
LinkedList list = new LinkedList();// 기본적으로 Object 타입을 저장
LinkedList<String> list1 = new LinkedList<>(); // 문자열 데이터를 저장
LinkedList<String> list2 = new LinkedList<String>(otherList);// 다른 컬렉션을 생성자에 입력LinkedList의 선언은 ArrayList와 동일하다. 하지만 ArrayList처럼 초기 값을 미리 지정하는 생성자는 제공되지 않는다. 배열처럼 미리 공간을 할당하고 사용하는 방식이 아닌 데이터가 추가될 때마다 노드들이 생성되어 참조 체인에 추가되는 방식이기 때문이다.
LinkedList를 선언할 때, 어떤 데이터를 저장할지 지네릭(Generic)을 이용해서 써줘야한다. 물론 생략해도 된다. LinkedList에 타입을 생략할 경우 Object 타입이 지정되어 임의의 타입을 LinkedList에 저장할 수 있게 된다. 하지만 이 경우에는 특정 리스트가 다루는 타입 체크를 컴파일 타임에 할 수 없어서 런타임에 타입에러(Type Cast Exception)가 발생할 수 있다.
다른 컬렉션 객체를 생성자의 입력으로 받아 LinkedList 객체를 생성함과 동시에 초기화 할 수도 있다.
LinkedList 값 추가
LinkedList는 add() 메소드를 이용해서 값을 추가할 수 있다.
list.add("Data1"); // "Data1" 문자열 추가
list.add(1, "Data2"); // 1번자리에 "Data2" 문자열 추가
list.addFirst("Data3"); // 첫 번째 자리에 "Data3" 문자열 추가
list.addLast("Data4"); // 마지막 자리에 "Data4" 문자열 추가add() 메소드에는 여러가지 종류들이 있다. addFirst()는 LinkedList의 맨 첫 번째 위치에 새로운 데이터를 추가하는 것이고, addLast()는 맨 마지막 위치에 데이터를 추가한다. 기본 add() 메소드는 addLast()와 동일하다. add() 메소드에 인덱스 값을 사용한 경우 인덱스에 해당하는 위치에 새로운 값을 추가한다. 이 동작은 특정 위치까지의 탐색을 필요로하기 때문에 O(n) 시간이 소요된다. (addFirst, addLast는 O(1)이면 된다)
add() 메소드와 함께 offser() 메소드도 있는데 동일한 동작을 한다.
LinkedList 값 제거
LinkedList는 remove() 메소드와 clear() 메소드를 이용해서 값을 지울 수 있다.
list.remove(); // 첫 번째 값 제거
list.remove(3); // 3번째 값 제거
list.removeFirst(); // 첫번째 값 제거
list.lastFirst(); // 마지막 값 제거
list.clear(); // 모든 값 제거add() 메소드처럼 remove() 메소드 역시 직관적이다. removeFirst() 메소드는 첫 번째 노드를 삭제하고, removeLast() 메소드는 마지막 노드를 삭제한다. 기본 remove() 메소드는 removeFirst()와 동일하며, 인덱스 값을 준 경우 해당 노드까지 탐색을 하고 나서 삭제를 하기 때문에 O(n) 시간이 소요된다.
LinkedList에 저장되어 있는 전체 값을 삭제하려는 경우 clear() 메소드를 실행하면 된다. 이 메소드 역시 참조 체인을 따라가면서 값들을 null로 닦아주기 때문에 O(n) 시간이 소요된다. (그렇지 않으면 GC가 잘 안되거나 느리게 될 수도 있다.)
LinkedList 사이즈
다른 컬렉션 타입들처럼 LinkedList 역시 저장하고 있는 데이터의 개수를 확인할 수 있는 메소드를 제공한다.
list.size(); // LinkedList에 들어있는 엘리먼트의 개수LinkedList 값 출력
list.get(3); // 3번째 값을 출력LinkedList 순회
for 문이나 Iterator를 이용해서 LinkedList의 엘리먼트들을 순회할 수 있다. 모든 데이터들을 출력할 때 유용하다.
// for 문을 이용한 순회
for (String data : list) {
System.out.println(data);
}
// iterator를 이용한 순회
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}LinkedList 값 검색
LinkedList에 특정 값이 저장되어 있는지 확인하는 메소드도 제공된다.
list.contain("Data2"); // "Data2"라는 문자열이 LinkedList에 저장되어 있는지. 있으면 true 리턴
list.indexOf("Data3"); // "Data3"이 저장되어 있는 위치 리턴. 없으면 -1 리턴
댓글