[Java] LinkedList

LinkedList란?

연결 리스트(LinkedList)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다.
데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다.
Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않는다.
중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에
ArrayList에 비해서 데이터의 추가나 삭제가 용이하나 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있다.

결론 : 검색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋다.

출처 : https://coding-factory.tistory.com/552

ArrayList는 내부 배열에 객체를 저장해서 인덱스로 관리하지만 LinkedList는 위와 같이 인접 참조를 링크해서 체인처럼 관리한다.

---

LinkedList 사용법

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));//생성시 값추가

LinkedList는 초기의 크기를 미리 생성할 수 없다. LinkedList 선언 시 LinkedList list = new LinkedList()로 선언하고 내부에 임의의 값을 넣어 사용할 수도 있지만 이렇게 사용할 경우 내부의 값을 사용할 때 캐스팅(Casting)을 해야하고 잘못된 타입으로 캐스팅을 한 경우엔 에러가 발생하기에 위와 같은 방식은 추천하지 않는다. LinkedList를 생성할때 사용 타입을 명시해주는 것이 좋다.
JDK5.0 이후부터 자료형의 안정성을 위해 제네릭스(Generics)라는 개념이 도입되었다.
LinkedList<Integer> list = new LinkedList<Integer>();라면 int만 사용할 수 있고 다른 타입은 사용이 불가능하다.

제네릭스? 선언할 수 있는 타입이 객체 타입이다. int는 기본 자료형이기 때문에 들어갈 수 없으므로 int를 객체화시킨 wrapper클래스를 사용해야 한다.

[Java] Wrapper클래스란?

[Java] Wrapper클래스란?

 

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));

출처 :&nbsp;https://coding-factory.tistory.com/552

LinkedList의 값이 추가되는 방식은 위의 그림과 같다. 먼저 인자로 받은 값을 가지고 Node를 생성하여 이전 노드는 추가되는 노드를 가리키게 하고 추가된 노드는 그 다음 노드를 가리키도록 지정한다.

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(); //모든 값 제거

출처 :&nbsp;https://coding-factory.tistory.com/552

LinkedList의 값이 제거되는 방식은 위의 그림과 같다. 삭제 대상 노드의 이전 노드가 삭제 대상 노드의 다음 노드를 가리키게 하고 삭제 대상 노드는 삭제된다.

LinkedList 크기 구하기

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

 

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()); //값 출력
}

 

LinkedList 값 검색

ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.contains(1)); //list에 1이 있는지 검색 : true
System.out.println(list.indexOf(1)); //1이 있는 index반환 없으면 -1

References : 이것이 자바다 15장 컬렉션 프레임워크
coding-factory.tistory.com/552