Algorithms

[JAVA] LinkedList 구현

kkkkkkkkkkkk 2022. 1. 10. 19:00

학습 내용

  • 추가
    • 요소 추가
    • 지정 인덱스에 요소 추가
  • 조회
    • 인덱스의 값 조회
    • 인덱스의 값을 비교
  • 수정
    • 지정 인덱스에 요소 수정
  • 삭제
    • 요소 삭제
    • 초기화 ( size, node clear )

 

Node.Class

public class Node<E> {

    public E data;
    public Node next;

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

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

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

}

data 는 요소를 뜻하고 next 는 다음 node 를 참조하는 뜻을 가집니다.

 

구현부

 

필드

private int size;
private Node head;

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

기본 사이즈와 첫번째 node를 head 라 참조하였고 생성시에는 초기화를 진행 하였습니다.

추가

1. 요소 추가

public boolean add(E element) {
    if (head == null) {
        head = new Node(element);
    } else {
        Node node = head;
        while (node.next != null){
            node = node.next;
        }
        node.next = new Node(element);
    }
    size++;
    return true;
}

첫 번째 node 가 null 일 시에는 새로운 Node 를 생성하여 요소를 추가해줍니다.

그렇지 않다면 첫번째 node를 생성하여 다음 node 가 null 이 아닐 때 까지다음 node 를 추가해주는 루프를 돕니다.

그리고 다음 node 에 요소를 새로 추가해줍니다.

다음으로 size를 쉬프트 해줍니다.

 

다음 node 가 null 이 아닐 때 까지 루프를 돌기 때문에 node 의 개수에 비례하여 시간이 걸립니다.

그러므로 시간 복잡도는 O(n)으로 보입니다.

 

 

1.2 지정 인덱스에 요소 추가

private Node getNode(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    Node node = head;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}
public void add(int index, E element) {
    if (index == 0) {
        head = new Node(element, head);
    } else {
        Node node = getNode(index - 1);
        node.next = new Node(element, node.next);
    }
    size++;
}

index 가 0 일 시에 node를 생성하여 요소와 첫번째 node인 head 를 생성합니다.

그렇지 않다면 헬퍼 메서드인 getNode를 사용하여 index - 1 자리의 node에 요소와 다음 node 를 저장합니다.

그리고나서 size 를 늘립니다.

 

add 메서드는 헬퍼 메서드를 빼면 상수 시간을 가지므로 시간 복잡도는 O(1) 입니다. 하지만 헬퍼 메서드의 시간 복잡도는 O(n) 이므로 add 메서드는 O(n) 이라는 시간 복잡도를 가집니다.

조회

 

1. 인덱스의 값 조회

public E get(int index) {
    return (E) getNode(index).data;
}

헬퍼 메서드를 사용하여 해당 index 의 node data를 가져옵니다.

 

헬머 메서드를 사용하여 시간 복잡도는 O(n) 으로 보입니다.

 

 

1.2 인덱스의 값을 비교

private boolean equals(Object target, Object data) {
    if (target == null) {
        return data == null;
    } else {
        return target.equals(data);
    }
}
public int indexOf(Object target) {
    Node node = head;
    for (int i = 0; i < size - 1; i++) {
        if (equals(target, node.data)) {
            return i;
        }
        node = node.next;
    }
    return -1;
}

첫번쨰 node 값을 가지고 반복문을 통하여 target 과 node data 를 비교하고 일치하면 인덱스 값 리턴 해주고 node에 다음 node를 참조해줍니다. 

값이 다를 시 -1 을 리턴 해줍니다.

 

헬퍼 메서드인 equals 는 O(1) 이라는 시간 복잡도를 가지고 indexOf 메서드는 O(n) 이라는 시간 복잡도를 가집니다.

 

수정

 

1. 지정 인덱스에 요소 수정

public E set(int index, E element) {
    Node<E> node = getNode(index);
    E oldVal = node.data;
    node.data = element;
    return oldVal;
}

index 값을 받아와 node 를 얻어옵니다. 이 node 에 data를 입력 받은 element를 넣어주고 리턴 해줍니다.

헬퍼 메서드 getNode의 시간 복잡는 O(n) 이므로 해당 set 메서드는 O(n) 이라는 시간 복잡도를 가지게 됩니다.

 

삭제

 

1. 요소 삭제

public E remove(int index) {
    E element = get(index);
    if (index == 0) {
        head = head.next;
    } else {
        Node node = getNode(index - 1);
        node.next = node.next.next;
    }
    size--;
    return element;
}

index 가 0 일 시에 첫번째 node 에 다음 node 값을 넣고 아닐 시에는 index -1 자리의 node의 정보를 node.next의 객체를 건너뛰고 node.next.next 객체를 저장합니다.

그리고 size 를 줄여주고 요소를 반환 해줍니다.

 

시간복잡도는 O(n) 으로 보여집니다.

 

 

1.2 초기화 ( size, node clear)

public void clear() {
    head = null;
    size = 0;
}

해당 메서드의 시간 복잡도는 O(1) 로 보여지는데 JVM의 가비지컬렉터가 같이 동작하므로 요소의 개수의 비례하여 연산 시간이 걸립니다.

그러므로 시간 복잡도는 O(n) 으로 보여집니다.