[자료구조] 링크드리스트(Linkde List)

링크드리스트 (Linked List)

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조.

구조

• 노드(Node) : 데이터 저장 단위(데이터, 포인터로 구성)
• 포인터(Pointer) : 각 노드 안에서, 다음이나 이전 노드와의 연결 정보를 가지고 있는 공간

장점

• 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다.

단점

• 배열이나 트리구조와는 달리 특정 위치의 데이터를 검색할땐 O(n)의 시간이 걸린다.

종류

단일 연결 리스트

• 각 노드에 자료공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

이중 연결 리스트

• 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

원형 연결 리스트

• 일반적인 연결리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

구현

단일 연결 리스트

• 노드 구성

  public class Node<T> {
    T data;
    Node<T> next = null;
  }

public class SingleLinkedList<T> {

    public Node<T> head = null;

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

        public Node(T data) {
            this.data = data;
        }
    }

    public void addNode(T data) {
        if (head == null) {
            head = new Node<T>(data);
        } else {
            Node<T> node = this.head;
            while (node.next != null) {
                node = node.next;
            }
            node.next = new Node<T>(data);
        }
    }

    public void printAll(){
        if (head != null) {
            Node<T> node = this.head;
            System.out.println(node.data);
            while (node.next != null) {
                node = node.next;
                System.out.println(node.data);
            }
        }
    }

}

사용법

선언

LinkedList list = new LinkedList();// Object타입으로 선언
LinkedList<User> users = new LinkedList<User>(); // User타입만 사용 가능
LinkedList<Integer> num = new LinkedList<Integer>();// int타입만 사용 가능
LinkedList<Integer> num2 = new LinkedList<>(); // new에서 타입 파라미터 생략가능
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));//생성시 값추가

참조

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8
https://coding-factory.tistory.com/552