연결리스트 개념 알아보기

1. 연결리스트란 (Linked List)?

    - 데이터를 링크로 연결해서 관리하는 자료구조

    - 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지 않음

 

2. 연결 리스트의 장점

    - 데이터 공간을 미리 할당할 필요 없다

    - 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이

 

3. 연결 리스트의 단점

    - 연결 구조를 위한 별도 데이터 공간 필요

    - 연결 정보를 찾는 시간이 필요 (접근 속도가 상대적으로 느림)

    - 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요

 

4. 연결 리스트의 기본 구조

    - 노드(Node)

        - 데이터 저장 단위로, 값과 포인터로 구성

연결리스트 예시

 

단방향 리스트를 기준으로 데이터를 추가하는 예시를 살펴보자

        - 가장 앞에 데이터 추가

                                        1. 추가할 데이터를 담을 노드 생성

                                        2. 링크 연결 작업

                                        3. head 이전 작업

 

        - 가장 뒤에 데이터 추가

                                         1. 추가할 데이터를 담을 노드 생성

                                         2. head로 부터 끝 노드까지 순회

                                         3. 링크 연결 작업

 

        - 중간에 데이터 추가

                                      1. 추가할 데이터를 담을 노드 생성

                                      2. head로 부터 데이터를 추가 위치 직전 노드까지 순회

                                      3. 링크 연결 작업

                                       * 주의할점 : 중간에 링크가 끊기지 않도록 연결 작업 필요.

                                            - new_node.next 에 data1.next 로 연결

                                            - data1.next에 new_node 연결

 

단방향 리스트를 기준으로 데이터를 삭제하는 예시를 살펴보자

   * Java의 경우 GC(Garbage Collection) 기능이 존재하여 메모리를 알아서 회수한다.

      그러므로 null 처리 또는 링크를 끊어주면 된다.

    - 가장 앞에 데이터 삭제

                                               1. 삭제 대상 노드 지정(delete_node)

                                               2. head 이전 작업

                                               3. delete_node 삭제

    - 가장 뒤에 데이터 삭제

                                           1. head로 부터 가장 끝까지 순회

                                           2. 끝 노드 삭제

                                           3. 삭제 이전 노드의 링크 처리

    - 중간에 데이터 삭제

                                  1. head로부터 삭제 대상 노드까지 순회 및 해당 노드 지정(delete_node)

                                  2. 삭제 대상 이전/이후 노드의 링크 연결 작업

                                  3. delete_node 삭제

 

연결리스트 경우 LinkedList가 연결리스트를 구현한 클래스이다. 그렇기 때문에 추가 삭제 를 쉽게 구현이 가능하다.

// 노드 import java.util.LinkedList; class Node { } public class Main {     public static void main(String[] args) {                 LinkedList<Node> list = new LinkedList<>();     } }

- 노드 클래스를 생성한 후 제너릭 변수로 선언해서 사용하면 된다.