1. LinkedList란?
연결 리스트(LinkedList)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다. Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있다. 그러므로 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋다.
ArrayList는 내부 배열에 객체를 저장해서 인덱스로 관리하는데 비해서 LinkedList는 위와 같이 인접 참조를 링크해서 체인처럼 관리한다.
2. ArrayList와 LinkedList의 차이
위 사진을 보면 알 수 있듯 ArrayList는 index가 있고, LinkedList는 각 원소마다 앞,뒤 원소의 위치값을 가지고 있다.
이러한 각각의 특징은 조회, 삽입, 삭제시에 성능의 차이를 발생시킨다.
1. ArrayList
ArrayList는 기본적으로 배열을 사용한다. 하지만 일반 배열과 차이점이 존재한다.
일반 배열은 처음에 메모리를 할당할 때 크기를 지정해주어야 하지만,
ArrayList는 크기를 지정하지 않고 동적으로 값을 삽입하고 삭제할 수 있다.
조회
ArrayList는 각 데이터의 index를 가지고 있고 무작위 접근이 가능하기 때문에, 해당 index의 데이터를 한번에 가져올 수 있다.
데이터 삽입과 삭제
데이터의 삽입과 삭제시 ArrayList는 그만큼 위치를 맞춰주어야 한다.
위의 사진으로 예를들면 5개의 데이터가 있을 때 맨 앞의 2를 삭제했다면 나머지 뒤의 4개를 앞으로 한칸씩 이동해야 한다.
삽입과 삭제가 많다면 ArrayList는 비효율적이다.
LinkedList
LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어 있어 참조하려는 원소에 따라 처음부터 정방향 또는 역순으로 순회 가능
(배열의 단점을 보완하기 위해 LinkedList가 고안되었다.)
조회
LinkedList는 순차적 접근이기 때문에 검색의 속도가 느리다.
데이터 삽입과 삭제
LinkedList는 데이터를 추가·삭제시 가리키고 있는 주소값만 변경해주면 되기 때문에 ArrayList에 비해 상당히 효율적이다.
위의 사진으로 예를들면 2번째 값을 삭제하면 1번째 노드가 3번째 노드를 가리키게 하기만 하면 된다.
이처럼 조회시에는 ArrayList가 우위에 있지만, 삽입/삭제 시에는 LinkedList가 뛰어난 성능을 보여준다.
소량의 데이터를 가지고 사용할 때는 사실 큰 차이가 없지만, 정적인 데이터를 활용하면서 조회가 빈번하다면 ArrayList를 사용하는 것이 좋고, 동적으로 추가/삭제 요구사항이 빈번하다면 LinkedList를 사용하는 것이 좋다.
3. LinkedList 사용법
1. LinkedList 선언
LinkedList list = new LinkedList();//타입 미설정 Object로 선언된다.
LinkedList<Student> members = new LinkedList<Student>();//타입설정 Student객체만 사용가능
LinkedList<Integer> num = new LinkedList<Integer>();//타입설정 int타입만 사용가능
LinkedList<Integer> num2 = new LinkedList<>();//new에서 타입 파라미터 생략가능
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));//생성시 값추가2. LinkedList 값 추가
LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(1);//가장 앞에 데이터 추가
list.addLast(2);//가장 뒤에 데이터 추가
list.add(3);//데이터 추가
list.add(1, 10);//index 1에 데이터 10 추가
LinkedList<Student> list = new LinkedList<Student>();
Student student = new Student(name,age);
members.add(student);
members.add(new Member("홍길동",15)); LinkedList에 값을 추가하는 방법은 여러 개가 있는데 대중적으로 add(index, value) 메소드를 사용한다. index를 생략하면 가장 마지막에 데이터가 추가된다. addFirst(value)함수를 사용하게 되면 가장 앞에 있는 Header의 값이 변경되고 addLast(value) 메소드를 사용하면 LinkedList 맨 뒤에 데이터가 추가된다.
3. LinkedList 값 삭제
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3,4,5));
list.removeFirst(); //가장 앞의 데이터 제거
list.removeLast(); //가장 뒤의 데이터 제거
list.remove(); //생략시 0번째 index제거
list.remove(1); //index 1 제거
list.clear(); //모든 값 제거
4. LinkedList 크기 구하기
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.size()); //list 크기 : 35. LinkedList 값 출력
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.get(0));//0번째 index 출력
for(Integer i : list) { //for문을 통한 전체출력
System.out.println(i);
}
Iterator<Integer> iter = list.iterator(); //Iterator 선언
while(iter.hasNext()){//다음값이 있는지 체크
System.out.println(iter.next()); //값 출력
}6. LinkedList 값 검색
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.contains(1)); //list에 1이 있는지 검색 : true
System.out.println(list.indexOf(1)); //1이 있는 index반환 없으면 -1