[JAVA] LinkedList 개념, 사용법 알아보기

 

📑 LinkedList란?

 

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

 

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

 

 

 

ArrayList는 내부 배열에 객체를 저장해서 인덱스로 관리하는데 비해서 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, 3));//생성시 값 추가

 

LinkedList 선언은 ArrayList 선언 방식과 같지만 LinkedList에서는 초기의 크기를 미리 생성할 수는 없다. LinkedList를 생성할 때 LinkedList에 사용 타입을 명시해주는 게 좋다. (캐스팅 에러를 방지하기 위해서) JDK 이후부터 자료형의 안정성을 위해 제너릭스라는 개념이 도입되었다. 

 

 

📑 LinkedList 값 추가 

 

LinkedList list = new LinkedList(); //타입 미설정 Object로 선언된다.
list.addFirst(1); //가장 앞에 데이터 추가
list.addLast(2); //가장 뒤에 데이터 추가
list.add(3);//데이터 추가
list.add(1, 10);//index 1에 데이터 10 추가
System.out.println(list); //[1, 10, 2, 3]

 

 

LinkedList에 값을 추가하는 방법은 여러개가 있는데 대중적으로 add(index,value) 메서드를 사용한다. index를 생략하면 가장 마지막에 데이터가 추가된다. addFirst(value) 함수를 사용하게 되면 가장 앞에 있는 Header의 값이 변경되고 addLast(value) 메서드를 사용하면 LinkedList맨 뒤에 데이터가 추가된다. 

 

 

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

 

 

LinkedList에 값을 제거하는 방법도 값을 추가하는것과 비슷하다. 

 

 

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

 

 

---

[참고]

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