자바 기초 알고리즘 - LinkedList 직접 구현하기 - 2

7. add 구현하기

이제 addFirst와 addLast가 아닌 특정 인덱스에 data를 삽입하는 add를 구현해보도록 하겠습니다.

 

우리는 이제 get을 통하여 특정 인덱스의 Node에 접근을 할 수 있었습니다.

 

그럼 add를 구현하기 아주 쉬워지는데요.

 

0번째 인덱스에 데이터를 삽입하는 경우는 addFirst와 같으니 addFirst를 써주고

 

그 외의 인덱스에 추가하는 것은 해당 인덱스와 그 이전의 인덱스 사이에 노드를 넣어주는 것이기 때문에

 

그 두개를 받고 next를 이어주기만 하면 됩니다.

 

public void add(int index, int data){
            if(index==0){
                addFrist(data);
            }else{
                Node newNode = new Node(data);
                Node prev = get(index-1);
                Node next = get(index);
                prev.next = newNode;
                newNode.next = next;
                size++;
                }
}

 

이런 느낌이죠. index가 0이라면 addFirst를 해주면 되고, 그 이외에는 새로운 노드를 만들어서 데이터를 넣어준뒤

 

이전 인덱스와 해당 인덱스의 노드를 받아서 next로 이어주면 끝

 

그런데, addFirst와 addLast를 구현할 때 중요한게 head값과 tail값이었잖아요?

 

인덱스가 0일때는 addFirst를 호출하니 상관 없는데, 마침 해당 인덱스가 마지막 인덱스였다면 tail값을 수정해주는 작업이 필요합니다.

 

간단하게 newNode의 next가 null이라면 tail을 newNode로 바꿔주면 됩니다.

 

 

public void add(int index, int data){
            if(index==0){
                addFrist(data);
            }else{
                Node newNode = new Node(data);
                Node prev = get(index-1);
                Node next = get(index);
                prev.next = newNode;
                newNode.next = next;
                size++;
                if(newNode.next == null){
                    this.tail = newNode;
                }
            }

        }

 

8. removeFirst 구현하기

 

removeFirst는 매우 간단합니다.

 

LinkedList의 head값을 head.next 값으로 바꿔주기만 하면 되니까요

public int removeFirst(){
            Node node = this.head;
            this.head = head.next;
            size--;
            return node.data;
        }

매우 쉽습니다.

 

9. remove 구현하기

 

그럼 이제 특정 인덱스의 값을 remove하는 것을 알아보도록 하겠습니다.

 

add와 크게 다르지 않습니다. 만약 첫번째 인덱스를 remove한다면 removeFirst를 실행해주고,

 

그게 아니라면 해당 인덱스의 이전 인덱스 노드와 다음 인덱스 노드를 받아서 그 두개를 다시 이어주면 되니까요.

 

하지만, add를 할 때와 마찬가지로 우리가 삭제하려는 값이 마지막 인덱스라면 tail;값의 변경이 필요하게 될겁니다.

 

public int remove(int index){
            if(index==0){
                return removeFirst();
            }else{
                Node selectedNode = get(index);
                Node prev = get(index-1);
                Node nextNode = prev.next.next;
                prev.next = nextNode;
                if(selectedNode == tail){
                    this.tail = prev;
                }
                size--;
                return selectedNode.data;
            }
        }

 

10. removeLast 구현하기

 

removeLast remove에 size-1을 실행하면 됩니다.