자료구조 - LinkedList

LinkedList란?

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조
• 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당
• ArrayList에 비해 데이터의 추가나 삭제가 용이
• 인덱스가 존재하지 않으므로 특정 요소에 접근하기위해선 순차 탐색이 필요

탐색 , 정렬 : ArrayList
데이터의 추가, 삭제 : LinkedList

ArrayList처럼 내부 배열에 객체를 저장해서 인덱스로 관리하는 것이 아닌, 인접 참조를 링크해서 체인처럼 관리

출처 : https://www.javatpoint.com/ds-linked-list

사용

LinkedList list = new LinkedList();// 타입 설정 안해준 경우 Object로 선언
LinkedList<Integer> num = new LinkedList<>(); // int 타입 설정

// 추가
list.addFirst(1); // 가장 앞에 데이터 추가
list.addLast(2); // 가장 뒤에 데이터 추가
list.add(3); // 데이터 추가
list.add(1, 10); // index 1에 데이터 10 추가

// 삭제
list.removeFirst(); // 가장 앞의 데이터 제거
list.removeLast(); // 가장 뒤의 데이터 제거
list.remove(); // 생략시 0번째 index 제거
list.remove(1); // index 1 제거
list.clear(); // 모든 값 제거

// 크기 구하기
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.size()); // list의 크기 : 3

// 값 검색
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.contains(1)); // 1이 있는지 검색 true, 없는 경우 false
System.out.println(list.indexOf(1)); // 1이 있는 index반환 , 없는 경우 -1