2.2.5 이중 연결 리스트 (Double Linked List)

2.2.5 이중연결리스트

2.2.5.1 이중 연결 리스트의 개념

 

 

        -> 하나의 노드가 선행 노드와 다음 노드에 대한 두 개의 링크를 가지는 연결 리스트이다.

        -> 이중 연결 리스트는 헤드 노드라는 특별한 노드를 가진다. 

            헤드노드란 데이터를 가지지 않는 노드로써 첫번째 노드를 가리킨다.

 

 

2.2.5.2 이중 연결 리스트의 장,단점

 

장점	단점
양 방향 탐색이 가능하다.	추가적인 메모리 공간이 필요하며, 코드가 복잡해 진다.

 

 

 

 

 

 

 

2.2.5.3 이중 연결 리스트의 구조

 

 

        -> 이중 연결 리스트는 3개의 필드 (왼쪽 링크 필드, 데이터 필드, 오른쪽 링크 필드)로 이루어진다.

        -> 링크필드에는 포인터가 저장 된다.

  (1) 이중 연결 리스트의 초기 상태

       

      

            -> 초기상태에는 헤드노드만 존재한다.                          

            -> 헤드노드의 링크 필드는 헤드노드 자신을 가리킨다.                               

 

  (2) 이중 연결 리스트의 관계

     -> p == p -> llink -> rlink == p -> rlink -> llink 

     -> 어떤 노드를 가리키는 포인터 p가 자신의 왼쪽링크를 갔다가 오른쪽 링크를 가는 것은 p 자기자신을 

         가리킨다.

     -> 어떤 노드를 가리키는 포인터 p가 자신의 오른쪽 링크를 갔다가 왼쪽링크를 가는 것은 p 자기자신을 

         가리킨다.

     -> 즉 이중 연결 리스트는 양방향 링크를 이용하여 자기자신으로 돌아올 수 있다.

  (3) 이중 연결 리스트의 정의

 

      

 

 

 

 

2.2.5.4 이중 연결 리스트의 삽입

 

 

 

 

            1) 그림과 같은 순서로 포인터 값을 바꾸면 된다.

            2) 여기서 새로 만들어진 노드의 포인터를 먼저 바꿔야 한다.

            3) 왜냐하면 새로 만들어진 노드의 링크는 아무런 정보도 가지고 있지 않아서 변경해도 

               안전하기 때문이다.

 

 

 

 

 

2.2.5.5 이중 연결 리스트의 삭제

 

 

 

 

                  

                          1) 삭제 또한 그림과 같은 순서로 포인터를 변경 해 주면 된다.

          

      

2.2.5.5 이중 연결 리스트 주의점

  1) 이중 연결 리스트에서는 헤드 노드가 존재하므로 단순 연결 리스트처럼 헤드 포인터가 필요 없다.

  2) 헤드 노드는 포인터 변수가 아니고 구조체 변수임을 주의해야 한다.

  3) 그리고 이중 연결 리스트의 헤드노드는 반드시 사용하기 전에 초기화를 해야 한다.

        즉, 헤드의 링크 필드들이 자기 자신을 가리키도록 초기화를 하여야 한다.