List - LinkedList 이론과 구현

---

📌ArrayList vs. LinkedList

1) 공통점

- 동일한 타입의 객체 수집

- 메모리 동적 할당

- 데이터의 추가, 변경, 삭제 등의 메서드

 

2) 차이점

- 생성자로 저장공간의 크기 지정 불가

 List<Integer> aLinkedList - new LinkedList<Integer>(); //O
  List<Integer> aLinkedList - new LinkedList<Integer>(20); //X 불가!

- 데이터의 내부 저장 방식이 index기반이 아닌, 앞뒤 객체의 위치 정보를 저장

 

---

📌ArrayList<E> vs. LinkedList<E>의 데이터 추가 매커니즘

구분	ArrayList	LinkedList
추가, 삭제 (add, remove)	속도 늦음	속도 빠름
검색 (get)	속도 빠름	속도 늦음

 

 

#1. ArrayList의 데이터 추가

- 다음과 같이 데이터 삽입시, 삽입된 뒷부분 데이터의 index값을 전부 변경해야한다.

- 검색시, 인덱스를 통해 바로 접근, 특정 인덱스의 데이터를 O(1) 시간에 바로 검색

 

aList.add(2, '아');

 

 

 

#2. LinkedList의 데이터 추가

- 데이터 삽입시, 앞뒤 데이터의 위치정보만 변경

- 검색 시 O(n), 원하는 노드를 찾기 위해 처음부터 끝까지 순차적으로 검색

 

aLinkedList.add(2, '아');

 

 

---

📌List<E> 인터페이스 주요 메서드

- LinkedList도 마찬가지로 List<E> 인터페이스의 구현 클래스이기 때문에, 아래와같은 메서드를 그대로 사용할 수 있다.

구분	리턴타입	메서드 이름	기능
데이터 추가	boolean	add(E element)	매개변수로 입력된 원소를 리스트 마지막에 추가
	void	add(int index, E element)	index 위치에 입력된 원소 추가
	boolean	addAll(Collection<? Extends E> c)	매개변수로 입력된 컬렉션 전체를 마지막에 추가
	boolean	addAll(int index, Collection <? Extends E c)	index 위치에 입력된 컬렉션 전체를 추가
데이터 변경	E	set(int index, E element)	index 위치의 원소값을 입력된 원소로 변경
데이터 삭제	E	remove(in index)	index 위치의 원소값 삭제
	boolean	remove(Object o)	원소 중 매개변수입력과 동일한 객체 삭제
	void	clear()	전체 원소 삭제
리스트 데이터 정보추출	E	get(int index)	index 위치의 원소값을 꺼내어 리턴
	int	size()	리스트 객체 내에 포함된 원소 갯수
	boolean	isEmpty()	리스트의 원소가 하나도 없는지 여부 리턴
리스트 배열 변환	Object[]	toArray()	리스트를 Object 배열로 변환
	T[]	toArray(T[] t)	입력매개변수로 전달한 타입의 배열로 변환

 

예시코드)

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class LinkedListMethod {
    public static void main(String[] args) {

        List<Integer> linkedlist1 = new LinkedList<>();

        //#1. add(E element)
        linkedlist1.add(3);
        linkedlist1.add(4);
        linkedlist1.add(5);
        System.out.println(linkedlist1.toString()); // System.out.println(aList1);과 동일 : System.out.println시 자동으로 toString 호출

        //#2. add(int index, E element)
        linkedlist1.add(1, 6); //원소 삽입 : 나머지 원소는 뒤로 밀린다.
        System.out.println(linkedlist1);

        //#3. addAll(또다른 리스트 객체)
        List<Integer> linkedlist2 = new LinkedList<>();
        linkedlist2.add(1);
        linkedlist2.add(2);
        System.out.println(linkedlist2);
        linkedlist2.addAll(linkedlist1);
        System.out.println(linkedlist2);

        //#4. addAll(int index, 또 다른 리스트 객체)
        List<Integer> linkedlist3 = new LinkedList<>();
        linkedlist3.add(1);
        linkedlist3.add(2); //[1,2]
        linkedlist3.addAll(1, linkedlist3); //[1,1,2,2]
        System.out.println(linkedlist3);


        //#5. set(int index, E element)
        linkedlist3.set(1, 5); //[1,5,2,2]
        linkedlist3.set(3, 6); //[1,5,2,6]
//        aList3.set(4, 7); //예외발생 indexOutofBoundsException
        System.out.println(linkedlist3);

        //#6. remove(int index)
        linkedlist3.remove(1); // 1번 index 삭제 [1,2,6]
        System.out.println(linkedlist3);

        //#7. remove(Object o)
        linkedlist3.remove(new Integer(1)); //객체를 생성하여 삭제 요청
        System.out.println(linkedlist3);

        //#8. clear()
        linkedlist3.clear();
        System.out.println(linkedlist3);

        //#9. isEmpty()
        System.out.println(linkedlist3.isEmpty()); //true
        System.out.println(linkedlist3.isEmpty()); //false

        //#10 size()
        System.out.println(linkedlist3.size());
        linkedlist3.add(1);
        linkedlist3.add(2);
        linkedlist3.add(3);
        System.out.println(linkedlist3.size());

        //#11 get(int index)
        System.out.println("0번째 : " + linkedlist3.get(0));
        System.out.println("1번째 : " + linkedlist3.get(1));
        System.out.println("2번째 : " + linkedlist3.get(2));
        for(int i : linkedlist3){
            System.out.println(i);
        }

        for(int i = 0; i < linkedlist3.size(); i++){
            System.out.println(i + "번째 : " + linkedlist3.get(i));
        }

        //#12. toArray() List --> Array
        Object[] object = linkedlist3.toArray();
        System.out.println(Arrays.toString(object)); //[1, 2, 3]

        //#13. toArray(T[] t)
        Integer[] integer1 = linkedlist3.toArray(new Integer[1]); // [1, 2, 3]
        System.out.println(Arrays.toString(integer1));

        Integer[] integer2 = linkedlist3.toArray(new Integer[5]); // [1, 2, 3, null, null]
        System.out.println(Arrays.toString(integer2));
    }
}

 

 

---

📌ArrayList vs. LinkedList의 성능 비교

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ArrayListVsLinkedList {
    public static void main(String[] args){

        //#1. 데이터 추가 시간 비교
        List<Integer> aList = new ArrayList<>();
        List<Integer> lList = new LinkedList<>();

        long startTime = 0, endTime = 0;

        //@1-1 ArrayList 데이터 추가 시간
        startTime = System.nanoTime();
        for(int i = 0; i < 100000; i++){
            aList.add(0, i);
        }
        endTime = System.nanoTime();
        System.out.println("ArrayList 데이터 추가 시간 = " + (endTime - startTime) + " ns");
        
        //@1-2 LinkedList 데이터 추가 시간
        startTime = System.nanoTime();
        for(int i = 0; i < 100000; i++){
            lList.add(0, i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList 데이터 추가 시간 = " + (endTime - startTime) + " ns");

        System.out.println("========================");

        //@2-1 ArrayList 데이터 검색 시간
        startTime = System.nanoTime();
        for(int i = 0; i < 100000; i++){
            aList.get(i);
        }
        endTime = System.nanoTime();
        System.out.println("ArrayList 데이터 검색 시간 = " + (endTime - startTime) + " ns");

        //@2-2 LinkedList 데이터 검색 시간
        startTime = System.nanoTime();
        for(int i = 0; i < 100000; i++){
            lList.get(i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList 데이터 검색 시간 = " + (endTime - startTime) + " ns");


        System.out.println("========================");

        //@3-1 ArrayList 데이터 삭제 시간
        startTime = System.nanoTime();
        for(int i = 0; i < 100000; i++){
            aList.remove(0);
        }
        endTime = System.nanoTime();
        System.out.println("ArrayList 데이터 삭제 시간 = " + (endTime - startTime) + " ns");

        //@2-2 LinkedList 데이터 삭제 시간
        startTime = System.nanoTime();
        for(int i = 0; i < 100000; i++){
            lList.remove(0);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList 데이터 삭제 시간 = " + (endTime - startTime) + " ns");


    }
}

 

= 결과 =

데이터 추가/삭제에는 LinkedList가 우수.

데이터 검색에는 ArrayList가 우수하다.

결론적으로 정렬을 자주하는 경우엔 ArrayList를 사용하고 데이터의 추가/삭제가 많은 경우 LinkedList를 사용하는 것을 권장

 

 

---

💡LinkedList 구현

LinkedList를 다음과 같이 구현하였다.

public class MyLinkedList<E>{

    private static class Node<E> {
        E data;
        Node<E> next;

        Node(E data){
            this.data = data;
            this.next = null;
        }
    }

    private Node<E> head;
    private int size;

    public MyLinkedList(){
        this.head = null;
        this.size = 0;
    }
    
    //삽입하는 메서드
    public void add(E data) {
        Node<E> newNode = new Node<>(data);
        if(head == null){
            head = newNode;
        }else{
            Node<E> current = head;
            while(current.next != null){
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }
    
    //리스트의 특정 위치에 삽입하는 메서드
    public void add(int index, E data){
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException();
        }

        Node<E> newNode = new Node<>(data);

        if(index == 0){
            newNode.next = head;
            head = newNode;
        }else{
            Node<E> current = head;
            for(int i = 0; i < index - 1; i++){
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
        size++;
    }
    
    //특정 위치의 요소를 삭제하는 메서드
    public void remove(int index) {
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }

        Node<E> removeNode;
        if(index == 0){
            removeNode = head;
            head = head.next;
        }else{
            Node<E> current = head;
            for(int i = 0; i < index - 1; i++){
                current = current.next;
            }
            removeNode = current.next;
            current.next = removeNode.next;
        }
        size--;
    }

    public E get(int index) {
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }

        Node<E> current = head;
        for(int i = 0; i < index; i++){
            current = current.next;
        }
        return current.data;
    }

    public int size() {
        return size;
    }


}

 

 

---

 

 

정적 이너 클래스 Node<E>

 

- 연결 리스트의 노드를 나타내는 정적 이너 클래스 정의

- E data  : 노드가 저장할 실제 data 값

- Node<E> next : 다음 노드를 가리키는 참조 필드, 초기값은 null

private static class Node<E> {
    E data;
    Node<E> next;

    Node(E data){
        this.data = data;
        this.next = null;
    }
}

 

 

---

 

 

필드 및 생성자

 

- head : 리스트의 첫번째 노드를 가리킴, 초기값 null

- size : 리스트의 현재 크기 저장, 초기값 0

private Node<E> head;
private int size;

public MyLinkedList(){
    this.head = null;
    this.size = 0;
}

 

 

---

 

 

데이터 추가 (add)

 

1) add (E data)

public void add(E data) {  // 새로운 데이터를 리스트의 끝에 추가하는 메서드.
    Node<E> newNode = new Node<>(data);  // 새로운 노드를 생성하고 데이터 설정.
    if(head == null){  // 만약 리스트가 비어 있으면, 새로운 노드를 head로 설정.
        head = newNode;
    }else{
        Node<E> current = head;  // 리스트의 첫 번째 노드를 current로 설정.
        while(current.next != null){  // current의 next가 null이 아닐 때까지 계속 이동.
            current = current.next;
        }
        current.next = newNode;  // 마지막 노드의 next를 새로운 노드로 설정.
    }
    size++;  // 리스트 크기 증가.
}

 

 

2) add(int index, E data)

// 특정 위치에 데이터 추가하는 메서드
public void add(int index, E data){  // 주어진 index 위치에 데이터를 삽입하는 메서드.
    if(index < 0 || index > size){  // 유효하지 않은 인덱스 처리.
        throw new IndexOutOfBoundsException();  // 인덱스가 범위를 벗어나면 예외 발생.
    }

    Node<E> newNode = new Node<>(data);  // 새로운 노드 생성.

    if(index == 0){  // 만약 인덱스가 0이면, 새로운 노드를 head 앞에 삽입.
        newNode.next = head;
        head = newNode;  // head를 새 노드로 변경.
    }else{
        Node<E> current = head;  // current를 head로 설정.
        for(int i = 0; i < index - 1; i++){  // index-1 위치까지 current를 이동.
            current = current.next;
        }
        newNode.next = current.next;  // 새 노드의 next를 current의 next로 설정.
        current.next = newNode;  // current의 next를 새 노드로 설정.
    }
    size++;  // 리스트 크기 증가.
}

 

 

---

 

 

데이터 삭제 (remove)

 

public void remove(int index) {  // 주어진 index 위치의 요소를 삭제하는 메서드.
    if(index < 0 || index >= size){  // 유효하지 않은 인덱스 처리.
        throw new IndexOutOfBoundsException();  // 인덱스가 범위를 벗어나면 예외 발생.
    }

    Node<E> removeNode;  // 삭제할 노드를 담을 변수.
    if(index == 0){  // 만약 인덱스가 0이면, head를 삭제.
        removeNode = head;
        head = head.next;  // head를 다음 노드로 변경.
    }else{
        Node<E> current = head;  // current를 head로 설정.
        for(int i = 0; i < index - 1; i++){  // index-1 위치까지 current를 이동.
            current = current.next;
        }
        removeNode = current.next;  // 삭제할 노드를 current의 next로 설정.
        current.next = removeNode.next;  // current의 next를 삭제된 노드의 next로 설정.
    }
    size--;  // 리스트 크기 감소.
}

 

 

---

 

 

데이터 검색 (get)

 

 public E get(int index) {  // 주어진 index 위치의 데이터를 반환하는 메서드.
    if(index < 0 || index >= size){  // 유효하지 않은 인덱스 처리.
        throw new IndexOutOfBoundsException();  // 인덱스가 범위를 벗어나면 예외 발생.
    }

    Node<E> current = head;  // current를 head로 설정.
    for(int i = 0; i < index; i++){  // 인덱스까지 current를 이동.
        current = current.next;
    }
    return current.data;  // 해당 노드의 데이터를 반환.
}

 

 

---

 

 

리스트 크기 반환 (size)

 

public int size() {  // 리스트의 크기를 반환하는 메서드.
    return size;
}