[Java] 자료구조 - LinkedList

1. LinkedList

 

연결 리스트는 각 요소가 사슬처럼 서로 연결되어 있는 형태의 자료구조를 말합니다.

배열처럼 미리 준비된 공간에 원소를 집어넣는 것이 아니라 그 때 그 때 메모리를 할당하여 기존의 원소와 연결하는 방식이므로 공간 활용 및 삽입, 삭제에 있어서 유리합니다. // 삽입, 삭제 연산 시간 - O(1)

하지만 배열처럼 인덱스를 이용하여 바로 원소에 접근할 수 없고 시작 지점부터 타고 타고 이동해서 원하는 원소에 접근할 수 있다는 것이 단점입니다. // 탐색 시간 - O(n)

 

 

연결 리스트에는 리스트의 시작점을 가리키는 포인터 (first)가 필요합니다.

그리고 각 원소들은 값을 저장하는 공간과, 다음 원소에 대한 주소를 저장하는 공간이 필요합니다.

C에서는 노드를 data 필드와 link 필드를 가진 구조체로 선언하고,

first를 노드에 대한 포인터로 선언하여 쉽게 구현할 수 있습니다.

 

2. Java 에서는...

 

1.2 버전부터 LinkedList 클래스를 제공하고 있습니다.

LinkedList 클래스는 이중연결리스트로,

first와 last 포인터를 통해서 양쪽 방향에서 접근할 수 있고,

각 노드에서 양쪽 방향으로 이동이 가능합니다.

아래와 같이 선언하여 연결 리스트를 만들 수 있습니다.

LinkedList<Integer> list = new LinkedList<>();

 

3. 메서드

 

기본적인 삽입, 삭제 메서드는 스택이나 큐와 유사합니다.

add, offer, push / poll, remove, pop / peek  https://co1nam.tistory.com/57?category=918197 참조

차이점이라면 pollFirst() pollLast() 같은 식으로 리스트의 시작과 끝에서 삽입, 삭제가 가능하다는 점입니다.

 

		
        LinkedList<Integer> mem = new LinkedList<>();
        LinkedList<Integer> mem2 = new LinkedList<>();
        
        mem.add(1); // 리스트 끝에 1을 추가, offer(1)도 같다.
        mem.add(1,2); // 인덱스 1 위치에 2를 추가
        
        ArrayList<Integer> c = new ArrayList<>();
        c.add(3);
        c.add(4);
        c.add(5);

        mem.addAll(c); // Collection을 통째로 리스트에 붙임
        
        mem.addFirst(0); // 리스트 앞에 0을 추가
        mem.addLast(100); // 리스트 끝에 100을 추가

        mem2 = (LinkedList<Integer>) mem.clone(); // 리스트를 복제
        mem.clear(); // 리스트 초기화

        if(
            mem2.contains(0) // 리스트가 0을 포함하고 있다면 true
            // 0의 인덱스를 반환 리스트 앞에서부터 탐색 / 리스트 끝에서부터 탐색
            && mem2.indexOf(0) == mem2.lastIndexOf(0)
            // 리스트의 첫번째 원소를 반환
            && mem2.element() == mem2.getFirst() 
            // 리스트의 마지막 원소를 반환, 인덱스가 리스트크기 - 1인 원소를 반환
            && mem2.getLast() == mem2.get(mem2.size() - 1)
          ) System.out.println("pass");

        for(Object m : mem2.toArray()){ // 리스트를 배열로 변환
            System.out.print(m + " ");
        }
	System.out.println();
        mem2.pop(); // 리스트 첫번째 원소를 제거
        mem2.set(mem2.size() - 1, 6); // 리스트 마지막 위치의 원소를 6으로 변환

        for(Object m : mem2.toArray()){
            System.out.print(m + " ");
        }

 

<실행결과>