Linked List :연결 리스트

- 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조

- 노드에는 자료와 다음 요소를 가리키는 링크가 있다!

   노드 = 자료 + 다음 링크

- 자료가 추가될 때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 열결함.

- i 번 째 요소를 찾는 데 걸리는 시간은 요소의 수(n)에 비례  : O(n)

- jdk class: LinkedList

 

1. Node

---

- 각 노드에는 이전, 이후 노드에 대한 정보가 있다.

 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

 

 

2. LInked List 만드는 두 가지 방법

---

  첫 번째 방법은 head에 첫 번째 element를 입력하는 방법

  두 번째 방법은 head 더미노드로 첫 번째 element를 가르키기만 함. 

  측 두 번째 부터 첫 번째 element가 등장

 

 

3. LInked List의 method

---

 

1) add(index, element)

   리스트 내의 특정 튀치에 element 삽입

   해당 위치 이후 element들을 오른쪽으로 이동.

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

 

 

2) add(element)

   index를 지정 안할 경우 맨 마지막에 해당 element가 붙음.

 

3) remove(index)

index에 해당하는 element를 꺼내온다. 그리고 해당  index이후 elements를 왼쪽으로 이동시킴

public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}

 

 

4)예제

public class LinkedList {

    public static void main(String[] args) {
        java.util.LinkedList<Integer> linkedList = new java.util.LinkedList<>();

        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.add(5);
        System.out.println("linked list : " + linkedList.toString());

        linkedList.add(2,6);
        System.out.println("insert 6 to index 2 : " + linkedList.toString());

        linkedList.addFirst(7);
        System.out.println("add 7 to first : " + linkedList.toString());

        linkedList.addLast(8);
        System.out.println("add 8 to last : " + linkedList.toString());

        linkedList.removeFirst();
        System.out.println("remove first element: " + linkedList.toString());

        linkedList.removeLast();
        System.out.println("remove last element : " + linkedList.toString());

        linkedList.remove(3);
        System.out.println("remove index3 element : " + linkedList.toString());

    }
}

실행 결과.

linked list : [1, 2, 3, 4, 5]
insert 6 to index 2 : [1, 2, 6, 3, 4, 5]
add 7 to first : [7, 1, 2, 6, 3, 4, 5]
add 8 to last : [7, 1, 2, 6, 3, 4, 5, 8]
remove first element: [1, 2, 6, 3, 4, 5, 8]
remove last element : [1, 2, 6, 3, 4, 5]
remove index3 element : [1, 2, 6, 4, 5]