[TIL] 단일연결리스트 구현하기

*20221114의 회고

 

   오늘은 하루종일 단일연결리스트를 구현했다. 인프런에서 제공되는 무료 강의 'JAVA로 배우는 자료구조(권오흠)' 을 참고하였는데, 이해하는데 정말 큰 도움이 되었다. 실제 현업에서는 이미 구현되어 있는 컬렉션 프레임워크를 사용하겠지만, 실제로 구현해보면 개념을 더 확실히 이해할 수 있고 또 오래 기억에 잘 남을 것 같다. 자료구조를 공부하는 데 있어서 실제 코드로 구현하는 건 꼭 필요한 과정이라고 생각한다.

 

public class Node<T> {
    public T data;
    public Node<T> next;

    public Node(T item) {
        data = item;
        next = null;
    }
}
//노드 클래스 구현

   우선 노드클래스를 만들어 줬다. 멤버변수로 data와 다음에 올 노드객체를 만들어준다. 노드에 넣을 객체를 받는 생성자도 구현해 주었다.

 

//단일연결리스트 구현하기
public class MySingleLinkedList<T> {

    public Node<T> head; //첫 번째 노드의 주소
    public int size;

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

    public void addFirst(T item) {
        Node<T> newNode = new Node<T>(item);
        newNode.next = head; //새로운 노드에 원래 head가 가리키던 주소를 넣어줘야 함
        head = newNode; //(그래야 자기가 헤드가 되고, 원래 헤드 노드였던 것을 가리킬 수 있음)
        size++;
    }

    public void addAfter(Node<T> before, T item) {
        Node<T> newNode = new Node<>(item);
        newNode.next = before.next;
        before.next = newNode;
        size++;
    }

    public void add(int index, T item) { //index 위치에 새로운 노드 추가
        if(index < 0 || index > size)
            return;
        if(index == 0)
            addFirst(item);
        else {
            Node<T> q = getNode(index - 1);
            addAfter(q, item);
        }
    }

    public T removeFirst() {
        if (head == null)
            return null;
        T temp = head.data;
        head = head.next; //원래 head가 가리키고 있던 노드를 넣어줌 -> 원래 head 삭제
        size--;
        return temp;
    }

    public T removeAfter(Node<T> before) { //before 노드의 다음노드를 삭제
        if(before.next == null)
            return null;
        T temp = before.next.data;
        before.next = before.next.next;
        size--;
        return temp;
    }

    public T remove(int index) { //index에 해당하는 노드 삭제하고, 그 노드에 저장된 데이터를 반환
        if(index < 0 || index >= size)
            return null;
        if(index == 0)
            return removeFirst();
        Node<T> prev = getNode(index - 1);
        return removeAfter(prev);
    }

    public T remove(T item) { //item에 해당하는 노드를 찾아서 제거. -> 탐색도 해야함
        Node<T> p = head;
        Node<T> q = null; //p의 한칸 전의 노드를 가리킴
        while(p != null && !p.data.equals(item)) {
            q = p;
            p = p.next;
        }
        if(p == null)
            return null; //삭제할 노드가 존재하지 않을 때
        if(q == null)
            return removeFirst(); //삭제할 노드 전의 노드가 존재하지 않을 때 -> 노드가 하나밖에 없다는 뜻
        else
            return removeAfter(q);
    }

    public int indexOf(T item) { //item에 해당하는 노드의 index값 반환
        Node<T> p = head;
        int index = 0;
        while(p != null) {
            if(p.data.equals(item))
                return index;
            else {
                p = p.next;
                index++;
            }
        }
        return -1;
    }

    public Node<T> getNode(int index) { //연결리스트의 index번째 노드의 주소를 반환한다.
        if(index < 0 || index >=size)
            return null;
        Node<T> p = head;
        for(int i = 0; i < index; i++) {
            p = p.next;
        }
        return p;
    }


    public T get(int index) { //index번째 노드에 저장된 데이터를 반환한다
        if(index < 0 || index >= size)
            return null;
//        Node<T> p = head;
//        for(int i = 0; i < index; i++)
//            p = p.next;
//        return p.data;
        return getNode(index).data;
    }

    public T getFromLast(int index) { //뒤에서부터 index번째 노드에 저장된 데이터를 반환한다
        if(index < 0 || index >= size)
            return null;
        return getNode(size - index).data;
    }
}

 

   MySingleLinkedList 클래스를 생성한 후, 여러 기능의 메소드를 만들었다. 첫번째에 노드를 추가해주는 addFirst(), 매개변수로 받은 노드의 다음에 새로운 노드를 추가해주는 addAfter(), 이 두개를 이용하여 지정한 인덱스에 노드를 추가해주는 add(), 첫번째에 있는 노드를 삭제해주는 removeFirst(), 매개변수로 받은 노드의 다음노드를 삭제해주는 removeAfter(),  이 두개를 이용하여 지정한 인덱스의 노드를 삭제해주는 remove(), 지정한 노드의 인덱스값을 반환해주는 indexOf(), 지정한 인덱스 노드의 주소값을 반환해주는 getNode(), 지정한 인덱스 노드의 데이터값을 반환해주는 get(), 추가로 코테문제를 풀기 위해 내가 따로 만든 함수(뒤에서부터 지정한 인덱스만큼 떨어진 곳에 있는 노드의 값을 반환) getFromLast() 까지!

 

실제로 구현해보니 어렵지만 재밌기도 하고 신기하기도 하고 그랬다. 그래서 컬렉션프레임워크에 이미 구현되어있는 자료구조들을 쓸 수 있어서 참 감사하고 다행이라는 생각도 했다^^ ㅎㅎ 이제 또 다른 자료구조를 배우러 가야겠다... 알고리즘 강의 이번주 내로 들을 수 있을까...! 최대한 힘 닿는 데 까지 해보자~!!! 후후후 화이팅 ~!!!!!