4. 연결 리스트 - 패스트캠퍼스 백엔드 부트캠프 3기

1. 연결 리스트(Linked List)

• 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조이다.
• 노드(Node)는 실제 데이터를 저장하며, 다음 노드를 가리키는 링크(포인터)를 갖고 있다.
• 자료(노드)가 추가될 때는, 필요한 만큼의 메모리를 할당받고, 이전 노드와 링크로 연결한다.
  → (정해진 크기가 없으며, 동적으로 확장 가능)
• 자료를 추가하거나 삭제할 때는, 연결되는 링크만 조정하면 되므로, 해당 연산의 복잡도는 O(1)이다.
• 연결 리스트에서 n번째 요소를 찾기 위해서는, 순차적으로 링크를 따라가야 하므로, 탐색 시간 복잡도는 O(n)이 된다.

public class ListNode<E> {
    private E data;
    public ListNode<E> next;

    public ListNode() {
        data = null;
        next = null;
    }

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

    public ListNode(E data, ListNode<E> link) {
        this.data = data;
        this.next = link;
    }

    public E getData() {
        return data;
    }
}

 

public class MyLinkedList<E> implements ListInterface<E> {

    private ListNode<E> head;
    int count;

    public MyLinkedList() {
        head = null;
        count = 0;
    }
    @Override
    public void insertElement(int position, E data) {
        ListNode<E> tempNode = head;
        ListNode<E> newNode = new ListNode<E>(data);

        if (position < 0 || position > count) {
            System.out.println("오류");
            return;
        }

        if (position == 0) {
            newNode.next = head;
            head = newNode;
        } else {
            ListNode<E> preNode = null;
            for (int i = 0; i < position; i++) {
                preNode = tempNode;
                tempNode = tempNode.next;
            }

            newNode.next = preNode.next;
            preNode.next = newNode;
        }
        count++;
        return;
    }

    @Override
    public void addElement(E data) {
        ListNode<E> newNode;

        if (head == null) {
            newNode = new ListNode<E>(data);
            head = newNode;
        } else {
            newNode = new ListNode<E>(data);
            ListNode<E> temp = head;

            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
        count++;
    }

    @Override
    public E removeElement(int position) {

        ListNode<E> tempNode = head;

        if (position < 0 || position > count) {
            System.out.println("오류");
            return null;
        }

        //head.next가 head가 되면된다.
        if (position == 0) {
            head = tempNode.next;
        }
        // 중간 삭제
        else {
            for (int i = 0; i < position - 1; i++) {
                tempNode = tempNode.next;
            }
            tempNode.next = tempNode.next.next;
        }
        count--;
        return tempNode.getData();
    }

    @Override
    public E getElement(int position) {

        ListNode<E> tempNode = head;

        if (position < 0 || position > count) {
            return null;
        }

        if (position == 0) {
            return head.getData();
        }

        for (int i = 0; i < position; i++) {
            tempNode = tempNode.next;
        }

        return tempNode.getData();
    }

    public ListNode<E> getNode(int position) {
        ListNode<E> tempNode = head;

        if (position < 0 || position > count) {
            return null;
        }

        if (position == 0) {
            return head;
        }

        for (int i = 0; i < position; i++) {
            tempNode = tempNode.next;
        }

        return tempNode;
    }

    @Override
    public int getSize() {
        return count;
    }

    @Override
    public boolean isEmpty() {
        return head == null;
    }

    @Override
    public void removeAll() {
        head = null;
        count = 0;
    }

    @Override
    public void printAll() {
        if (count == 0) {
            System.out.println("isEmpty");
            return;
        }

        ListNode<E> tempNode = head;
        while (tempNode != null) {
            System.out.print(tempNode.getData());
            tempNode = tempNode.next;
            if( tempNode != null)
                System.out.print("ㅡ>");
        }
        System.out.println();
    }
}

public class MyLinkedTest {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addElement("A");
        list.addElement("B");
        list.addElement("C");

//        list.removeElement(3);
        list.printAll();

        list.removeElement(0);
        list.removeElement(0);
        list.printAll();

        list.insertElement(0, "A-1");
        list.printAll();
        System.out.println(list.getSize());

        list.removeElement(0);
        list.printAll();
        System.out.println(list.getSize());

        list.removeAll();
        list.printAll();
        list.addElement("A");
        list.printAll();
        System.out.println(list.getElement(0));
        list.removeElement(0);
    }
}