연결리스트

• 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조

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

• 삽입, 삭제 O(1), 탐색 O(n)

• 다음 노드를 가리키는 포인터는 다음 노드의 주소를 값으로 가지고 있음

• 맨 앞에 있는 노드를 헤드라고 함

  

  

종류

• 싱글 연결 리스트

  • 다음 노드를 가리키는 next 포인터만 가지는 연결 리스트

  • 이전 요소 접근에 매우 부적합

    • 탐색 시간이 O(n) 1000개의 데이터에 999번째 데이터는 노드를 999번 이동

  • 클래스

    class Node {
        Node next; // 다음 노드 주소를 저장하는 필드
        int data; // 데이터를 저장하는 필드
    };
    

• 이중 연결 리스트

  • next포인터와 이전 노드를 가리키는 prev 포인터도 가지는 연결 리스트

  • 단방향이던 이동 방향을 양방향으로 가능하게 해서 역순 검색이 가능하도록 함

  • 기본적으로 많이 사용되는 방식

    • 💡실제로 자바의 LinkedList는 이중 연결 리스트로 구현 되어 있음

  • 클래스

    class Node {
        Node next; // 다음 노드 주소를 저장하는 필드
        Node prev; // 이전 노드 주소를 저장하는 필드
        int data; // 데이터를 저장하는 필드
    };
    

• 원형 이중 연결 리스트

  • 첫 번째 노드와 마지막 노드를 각각 연결시켜 원형으로 만든 이중 연결 리스트
  • 티비 채널 순회나 오디오 플레이어 같이 데이터를 순차적 방식으로 처리하다 마지막 요소를 만나면 다시 처음 요소로 되돌아가는 곳에서 사용
  • 단일 연결 리스트 원형으로 연결한 ‘원형 싱글 연결 리스트’도 존재함, 하지만 잘 쓰이지 않음

🧱 자바 LinkedList 구조 & 사용법 - 정복하기