[자료구조] LinkedList 사용법 & 예제 (Java)

LinkedList

---

ArrayList는 배열을 사용하여 List를 구현한 클래스입니다. ArrayList와 다르게 LinkedList(연결 리스트)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조입니다. 각각의 데이터가 노드(Node)로 구성되어 연결이 되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당합니다.

 

출처: GeeksforGeeks

LinkedList 장점

 

데이터를 추가하거나 삭제하는 것이 원활합니다. 노드(Node)는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않습니다. 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이합니다.

 

LinkedList 단점

 

인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있습니다.

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

 

LinkedList 생성

 

// 자바에서 LinkedList를 사용하려면 아래 구문을 추가해주어야 합니다.
import java.util.LinkedList;

 

LinkedList 사용법

 

LinkedList list = new LinkedList();//타입 미설정 Object로 선언된다.
LinkedList<Student> members = new LinkedList<Student>();//타입설정 Student객체만 사용가능
LinkedList<Integer> integer = new LinkedList<Integer>();//타입설정 int타입만 사용가능
LinkedList<Integer> integer1 = new LinkedList<>();//new에서 타입 파라미터 생략가능
LinkedList<Integer> integer2 = new LinkedList<Integer>(Arrays.asList(1,2));//생성시 값추가

 

LinkedList 선언은 ArrayList선언 방식과 같지만 다른 점은 LinkedList에서는 초기의 크기를 미리 지정해 줄 수 없습니다.

 

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);
list.add(student);
list.add(new Student("Sam",15));

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

 

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에 값을 제거하는 방법도 값을 추가하는 것과 비슷합니다. removeFirst() 메서드를 사용하면 가장 첫 데이터가 removeLast()를 사용하면 가장 뒤에 있는 데이터가 삭제됩니다. remove(index, value)를 사용하여 특정 index의 값을 제거할 수도 있습니다. 값을 전부 제거하려면 clear() 메서드를 사용하면 됩니다.

 

LinkedList 크기 구하기

 

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

LinkedList의 크기를 구하려면 LinkedList의 size() 메소드를 사용하면 됩니다.

 

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의 get(index) 메소드를 사용하면 LinkedList의 원하는 index의 값이 리턴됩니다. 전체 출력은 대부분 for문을 통해서 출력을 하고 iterator를 사용해서 출력을 할 수도 있습니다. LinkedList의 경우 인덱스를 사용하여 연산을 수행할 수 있도록 get(index) 메소드를 제공하지만, 메서드 내부의 동작은 순차 탐색으로 이루어져 있어 ArrayList의 get(index) 메서드보다 속도가 느립니다.

 

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

LinkedList에서 찾고자 하는 값을 검색하려면 LinkedList의 contains(value) 메소드를 사용하면 됩니다. 만약 값이 있다면 true가 리턴되고 값이 없다면 false가 리턴됩니다. 값을 있는 index를 찾으려면 indexOf(value) 메소드를 사용하면 되고 만약 값이 없다면 -1을 리턴합니다.   

 

 

Reference

---

What is Linked List - GeeksforGeeks