[Data Structures & Algorithms] 연결 자료구조와 연결 리스트 (단순 연결 리스트와 연산 알고리즘)

🎯 연결 자료구조(Linked Data Structure)란?

연결 자료구조란 자료의 논리적 순서와 물리적 순서가 일치하지 않는 자료구조를 말한다.

각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되므로, 물리적 순서를 맞추기 위한 오버헤드가 발생하지 않는다는 특징이 있다.

 

---

 

🎯 연결 리스트(Linked List)란?

리스트를 연결 자료구조 형식으로 표현한 것을 연결 리스트(Linked List)라고 하며, 연결 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트로 구분할 수 있다.

 

---

 

❤️ 연결 리스트의 노드

: 연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조

 

노드의 논리적 구조
데이터 필드 (Data field)	링크 필드 (Link field)
원소의 값 저장	다음 노드의 주소 저장
저장할 원소 형태에 따라 1개 이상의 필드로 구성	포인터 변수를 사용하여 주소값 저장

 

---

 

🎯단순 연결 리스트 (Singly Linked List)란?

노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가지는 리스트를 단순 연결 리스트(Singly Linked List)라고 한다.

 

---

 

❤️ 단순 연결 리스트 알고리즘_ 1) 삽입 연산

① 삽입할 노드 준비  ==  메모리 할당
② 새 노드의 데이터 필드에 값 저장  ==  값 지정
③ 새 노드의 링크값 지정  ==  연결
④ 리스트의 앞 노드에 새 노드 연결  ==  연결

 

① 첫 번째 노드로 삽입하기

insertFirstNode(L, x)

    new <- getNode(); //메모리 할당
    new.data <- x; //값 지정
    new.link <- L; //리스트의 첫 번째 노드 주소를 새 노드의 링크 필드에 저장
    L <- new; //첫 번째 노드 주소 가진 포인터 L에 새 노드 주소 저장
    
end insertFirstNode()

 

 

② 중간 노드로 삽입하기

insertMiddleNode(L, pre, x)

    new <- getNode(); //메모리 할당
    new.data <- x; //값 지정
    
    if(L = NULL) then //공백 리스트인 경우
    {
        L <- new; //새 노드 주소를 리스트 포인터에 저장
        new.link <-NULL; //마지막 노드의 링크 필드에 NULL값 저장
    }
    else
    {
        new.link <- pre.link; //노드 pre의 링크 필드값을 new의 링크 필드에 저장
        pre.link <- new; //포인터 new값을 pre의 링크 필드에 저장
    }
    
end insertMiddleNode()

 

 

③ 마지막 노드로 삽입하기

insertLastNode(L, x)

    new <- getNode();
    new.data <- x;
    new.link <- NULL //마지막 노드가 될 것이니까 NULL 값 할당
    
    if (L = NULL) then //공백 리스트인 경우
    {
        L <- new; //리스트 포인터 L에 새 노드의 주소 저장
        return;
    }
    
    temp <- L; //임시포인터 temp에 리스트의 첫 번째 노드 주소 지정
    
    while (temp.link != NULL) do //마지막 노드를 찾을 때까지 링크 필드를 따라 이동
    {
        temp <- temp.link;
    }
    
    temp.link <- new;
    
end insertLastNode();

 

---

 

❤️ 단순 연결 리스트 알고리즘_ 2) 삭제 연산

① 삭제할 노드의 앞 노드 탐색
② 앞 노드에 삭제할 노드의 링크 필드값 저장
③ 삭제한 노드의 앞 노드와 삭제한 노드의 다음 노드 연결

 

① 리스트 L에서 포인터 pre가 가리키는 노드의 다음 노드(old)를 삭제하는 알고리즘

deleteNode(L, pre)

    if (L == NULL) then error; //공백 리스트인 경우 오류 처리
    else //공백 리스트가 아닌 경우
    {
        old <- pre.link; //pre의 다음 노드 주소를 포인터 old에 저장
        if (old = NULL) then return; //pre가 리스트의 마지막 노드인 경우
        pre.link <- old.link; //pre가 리스트의 마지막 노드가 아닌 경우 삭제 진행
        returnNode(old); //삭제한 노드 old의 메모리 반환
    }
    
end deleteNode()

 

---

 

❤️ 단순 연결 리스트 알고리즘_ 3) 노드 탐색 연산

① 노드 x 탐색 알고리즘

searchNode(L, x)
    
    temp <- L;
    
    while (temp != NULL) do //순회 포인터 temp가 NULL이 아닌 경우
    {
        if (temp.data == x)
        {
            return temp;
        }
        else
        {
            temp <- temp.link;
        }
    }
    
    return temp;
    
end searchNode()