[JAVA] LinkedList의 개념 및 사용법

LinkedList란 ?

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조

풀어쓰자면 다음과 같다.

데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다.

중간에 데이터를 추가하거나 삭제해도 인덱스가 당겨지거나 밀리는 현상이 없다. 따라서 ArrayList에 비해 데이터 추가/삭제가 용이하지만 인덱스가 없기 때문에 탐색 속도가 느리다. 따라서 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결리스트를 사용하는 것이 좋다.

 

LinkedList 사용법

1. LinkedList 선언

LinkedList list = new LinkedList();//타입 미설정. Object로 선언
LinkedList<Student> members = new LinkedList<Student>();//List 타입을 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 선언 시 LinkedList list = new LinkedList()로 선언하고 내부에 임의의 값을 넣어 사용할 수 있습니다. 하지만 이 경우 잘못된 타입으로 캐스팅(Casting, 형변환)을 한 경우 에러가 발생할 수 있습니다. 따라서 LinkedList를 생성할 때 타입을 명시해주는 것을 권장합니다.

 

2. LinkedList 값 추가

LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(10);//가장 앞에 데이터 추가
list.addLast(20);//가장 뒤에 데이터 추가
list.add(30);//데이터 추가
list.add(1, 10);//index 1에 데이터 10 추가

add(int index, Object) : index에 데이터를 추가합니다.

add(Object) : index를 생략한 경우 가장 마지막에 데이터가 추가 됩니다.

addFirst(Object) :  가장 앞에 데이터가 추가됩니다.

addLast(Object) : 가장 뒤에 데이터가 추가됩니다.

 

노드의 앞에 데이터가 삽입되는 경우 이전 노드는 추가되는 노드를 가리키게 되고, 추가되는 노드는 그 다음 노드를 가리킵니다. 아래는 예시입니다.

public static void main(String[] args)  {
        LinkedList<String> link = new LinkedList<String>();
        
        link.add("JAVA");
        link.add("Hello");
        link.add(1, "World");
        
        System.out.println(link);    // JAVA World Hello
        
        link.set(1, "Hello");        
 
        System.out.println(link);    // JAVA Hello Hello
    }
 

 

 

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

 

 

LinkedList 크기 구하기

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

LinkedList의 크기는 size()메소드를 사용합니다.

 

LinkedList 값 출력하기

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3,4,5));
 
                
for(Integer i : list) { //for문을 통한 전체출력
    System.out.println(i);
}
 
Iterator<Integer> iter = list.iterator(); //Iterator 선언 
while(iter.hasNext()){//다음값이 있는지 체크
    System.out.println(iter.next()); //값 출력
}

LinkedList는 for문이나 Iterator를 사용하여 값을 출력할 수 있습니다. 

LinkedList는 메소드 내부적으로 순차탐색을 하기 때문에 값을 get 해오는 시간이 ArrayList보다 오래 걸립니다.

 

 

 

참조: https://crazykim2.tistory.com/566, https://coding-factory.tistory.com/552