[Java] LinkedList 란? (LinkedList 구현해보기)

LinkedList 란

데이터를 저장하는 각 노드가 다음 노드의 주소를 알고 있다고 보면 간단히 이해할 수 있다. 

그림상으로는 다음과 같다.

LinkedList 구조

다음과 같은 구조를 가질 때 장점이 존재한다

 

추가 ,삭제에 용이하다(LinkedList는 이전 노드와 다음 노드를 참조하는 상태만 변경하면 됨 시작 복잡도 O(1))

LinkedList 추가 flow

 

하지만 단점도 존재한다.

 

LinkedList는 검색 시 모든 요소를 거쳐서 탐색해야 돼서 느리다 ( 시작 복잡도O(N) )

---

구현 Class

LinkedList 에서 추가 , 삭제 , 값 확인하는 로직만 구현하였음. 

public class LinkedList {
    private Node head;
    private Node tail;
    private int size = 0;

    class Node {
        // data -> value 를 저장하고 있는 필드
        private int data;
        // next  - > 다음 요소를 저장하고있는 필드
        private Node next;

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

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }
    // 0번째 에 new Node 를 추가하는 method;
    public Node firstNodeAdd(int value){
        Node newNode = new Node(value);
        //LinkedList 의 head 값이 null 이면 첫번째 요소임으로 head 와 tail 에 Node 저장
        if(head == null){
            this.head = newNode;
            this.tail = newNode;
        }else {
            //LinkedList 의 head 값이 null 아니면 n+1번째 요소임으로
            // newNode 의 next 에 현재 head 값 저장 , head 에 newNode 저장
            newNode.next = this.head;
            this.head = newNode;
        }
        size++;
        return newNode;
    }
    // 마지막 번째 에 new Node 를 추가하는 method;
    public Node add(int value){
        if(head ==null){
           return firstNodeAdd(value);
        }else {
            Node newNode = new Node(value);
            tail.next= newNode;
            tail=newNode;
            size++;
            return newNode;
        }
    }

    // 특정위치 에 new Node 를 추가하는 method;
    public Node add(int value, int position){
        Node newNode = new Node(value);
        if (position == 0){
            return firstNodeAdd(value);
        }else{
            Node node = node(position-1);
            Node temp = node.next;
            node.next = newNode;
            newNode.next=temp;
            if(newNode.next == null){
                this.tail=newNode;
            }
            size++;
        }
        return newNode;
    }
    // LinkedList 에 해당 요소가 존재하는지 확인하는 method;
    public boolean contains(Node checkNode){
        Node node = head;
        do{
            if(node ==checkNode){
                return true;
            }
            node = node.next;
        }while (head.next != null);
        return false;
    }

    // 특정위치에있는 요소 삭제.
    public Node remove(int position){
        if (position == 0) {
            Node node =node(position);
            this.head = node.next;
            size--;
            return node;
        }else {
            Node node = node(position-1);
            Node removeNode = node.next;
            node.next = removeNode.next;
            size--;
            return removeNode;
        }
    }

    // 특정위치에 있는 요소 반환하는 method
    private Node node(int position){
        Node node = head;
        for (int i = 0; i < position; i++) {
          node = node.next;
        }
        return node;
    }

    public int size(){
        return size;
    }

    @Override
    public String toString(){
        if(head == null){
            return "[]";
        }
        Node temp = head;
        String str = "[";
        while(temp.next != null){
            str += temp.data + ",";
            temp = temp.next;
        }
        str += temp.data;
        return str+"]";
    }
}

 

---

Test 코드

몇몇  method 와 filed 가  private로 선언되어서 자바 reflection을 이용하여

private 필드와 메서드에 접근하여 테스트 코드를 작성함 

class LinkedListTest {
    LinkedList linkedList;

    @BeforeEach
    void beforeEach(){
        linkedList = new LinkedList();
    }

    @Test
    @DisplayName("요소 last 인덱스에 추가")
    void add_success() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException, NoSuchFieldException {
        LinkedList.Node node = linkedList.add(1);
        Field field = node.getClass().getDeclaredField("data");
        field.setAccessible(true);
        int data = field.getInt(node);

        Method nodeMethod = LinkedList.class.getDeclaredMethod("node", int.class);
        nodeMethod.setAccessible(true);
        LinkedList.Node node1 = (LinkedList.Node) nodeMethod.invoke(linkedList, 0);
        Field field2 = node1.getClass().getDeclaredField("data");
        field2.setAccessible(true);
        int data2 = field2.getInt(node);

        assertThat(linkedList.size()).isEqualTo(1);
        assertThat(data).isEqualTo(data2);
    }

    @Test
    @DisplayName("요소 특정 위치 인덱스에 추가")
    void add_position_success() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException, NoSuchFieldException {
        linkedList.add(2);

        LinkedList.Node node = linkedList.add(1,0);
        Field field = node.getClass().getDeclaredField("data");
        field.setAccessible(true);
        int data = field.getInt(node);

        Method nodeMethod = LinkedList.class.getDeclaredMethod("node", int.class);
        nodeMethod.setAccessible(true);
        LinkedList.Node node1 = (LinkedList.Node) nodeMethod.invoke(linkedList, 0);
        Field field2 = node1.getClass().getDeclaredField("data");
        field2.setAccessible(true);
        int data2 = field2.getInt(node);

        assertThat(linkedList.size()).isEqualTo(2);
        assertThat(data).isEqualTo(data2);
    }

    @Test
    @DisplayName("요소 삭제")
    void remove_success() {
        linkedList.add(2);

        linkedList.remove(0);
        int size = linkedList.size();

        assertThat(size).isEqualTo(0);
    }

    @Test
    @DisplayName("요소 존재하는지 확인")
    void contain_Node(){
        LinkedList.Node add = linkedList.add(1);
        boolean contains = linkedList.contains(add);
        assertThat(contains).isTrue();
    }

}

 

 

그림출처: www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/

             marxtudor.com/linked-list-tutorial/

Linked List tutorial - Marxtudor

Linked List | Set 2 (Inserting a node) - GeeksforGeeks