JavaScript에서 'next'와 'previous' 속성으로 연결된 객체 배열 정렬하기

여러 페이지로 구성된 웹사이트를 예로 들어 보겠습니다. 아래 샘플 배열의 각 객체는 웹사이트의 한 페이지를 나타내며, next 속성(마지막 페이지가 아닌 경우)은 다른 객체의 id를 가리키고, previous 속성(첫 번째 페이지가 아닌 경우)은 바로 앞 객체의 id를 가리킵니다.

현재 이 객체들은 모두 무작위 순서로 뒤섞여 있습니다. 우리가 해야 할 일은 이 객체들을 원래의 올바른 순서대로 정렬하는 것입니다.

let arr = [
    { id: "1325asdfasdasd", next: "5345341fgdfgdd", previous:"545234123fsdfd" },
    { id: "das987as9dya8s", next: "3j12k3b1231jkj" },
    { id: "89ad8sasds9d8s", previous: "1j3b12k3jbasdd" },
    { id: "5345341fgdfgdd", next: "1j3b12k3jbasdd", previous:"1325asdfasdasd" },
    { id: "1423123123asfd", next: "545234123fsdfd", previous:"3j12k3b1231jkj" },
    { id: "1j3b12k3jbasdd", next: "89ad8sasds9d8s", previous:"5345341fgdfgdd" },
    { id: "3j12k3b1231jkj", next: "1423123123asfd", previous:"das987as9dya8s" },
    { id: "545234123fsdfd", next: "1325asdfasdasd", previous:"1423123123asfd" },
];

정렬이 완료되면 previous 속성이 없는 객체가 맨 처음, next 속성이 없는 객체가 맨 마지막에 위치해야 하고, 그 사이의 모든 객체는 next와 previous가 서로 올바른 id를 가리키도록 해야 합니다.

이 문제는 두 단계로 나누어 해결할 수 있습니다.

1단계 — Map 생성 및 시작 객체 찾기

먼저 배열 전체를 순회하면서 각 객체의 id를 키(key), 객체 자체를 값(value)으로 하는 Map을 만듭니다. 동시에 previous 속성이 없는 객체, 즉 첫 번째 페이지에 해당하는 객체를 별도의 변수에 저장해 둡니다.

const objectMap = new Map();
let firstObject;
const sortedArray = [];
for(const obj of arr){
    objectMap.set(obj.id, obj);
    if(!obj.previous){
        firstObject = obj;
    }
}

Map을 사용하는 이유는 id만으로 해당 객체를 O(1) 시간에 즉시 조회할 수 있기 때문입니다. 매번 배열을 다시 탐색하는 비효율을 피할 수 있습니다.

2단계 — next 속성을 따라가며 순서대로 배치

이제 저장해 둔 첫 번째 객체부터 출발하여, 각 객체의 next가 가리키는 다음 객체를 Map에서 찾아 정렬 배열에 차례로 추가합니다. next가 더 이상 존재하지 않으면(마지막 페이지에 도달하면) 반복이 종료됩니다.

for(let start = firstObject; start; start = objectMap.get(start.next)){
    sortedArray.push(start);
};
console.log(sortedArray);

완성된 전체 예제

지금까지 설명한 내용을 하나의 완전한 코드로 정리하면 다음과 같습니다.

let arr = [
    { id: "1325asdfasdasd", next: "5345341fgdfgdd", previous:"545234123fsdfd" },
    { id: "das987as9dya8s", next: "3j12k3b1231jkj" },
    { id: "89ad8sasds9d8s", previous: "1j3b12k3jbasdd" },
    { id: "5345341fgdfgdd", next: "1j3b12k3jbasdd", previous:"1325asdfasdasd" },
    { id: "1423123123asfd", next: "545234123fsdfd", previous:"3j12k3b1231jkj" },
    { id: "1j3b12k3jbasdd", next: "89ad8sasds9d8s", previous:"5345341fgdfgdd" },
    { id: "3j12k3b1231jkj", next: "1423123123asfd", previous:"das987as9dya8s" },
    { id: "545234123fsdfd", next: "1325asdfasdasd", previous:"1423123123asfd" },
];
const objectMap = new Map();
let firstObject;
const sortedArray = [];
for(const obj of arr){
    objectMap.set(obj.id, obj);
    if(!obj.previous){
        firstObject = obj;
    }
}
for(let start = firstObject; start; start = objectMap.get(start.next)){
    sortedArray.push(start);
};
console.log(sortedArray);

출력 결과

코드를 실행하면 콘솔에 다음과 같이 올바르게 정렬된 배열이 출력됩니다.

[
    { id: 'das987as9dya8s', next: '3j12k3b1231jkj' },
    {
        id: '3j12k3b1231jkj',
        next: '1423123123asfd',
        previous: 'das987as9dya8s'
    },
{
    id: '1423123123asfd',
    next: '545234123fsdfd',
    previous: '3j12k3b1231jkj'
},
{
    id: '545234123fsdfd',
    next: '1325asdfasdasd',
    previous: '1423123123asfd'
},
{
    id: '1325asdfasdasd',
    next: '5345341fgdfgdd',
    previous: '545234123fsdfd'
},
{
    id: '5345341fgdfgdd',
    next: '1j3b12k3jbasdd',
    previous: '1325asdfasdasd'
},
{
    id: '1j3b12k3jbasdd',
    next: '89ad8sasds9d8s',
    previous: '5345341fgdfgdd'
},
{     id: '89ad8sasds9d8s', previous: '1j3b12k3jbasdd' }
]

마무리 정리

이 접근 방식의 핵심은 Map을 활용한 것입니다. 단순히 매번 배열을 처음부터 탐색하면서 다음 객체를 찾는 방식은 O(n²)의 시간 복잡도를 갖지만, 위 예제처럼 Map으로 id 기반 조회를 하면 배열 순회 한 번 + 연결 순서 추적 한 번으로 O(n) 안에 정렬을 완료할 수 있습니다. 데이터 양이 많아질수록 그 성능 차이가 커지므로, 이런 연결 리스트 형태의 데이터를 정렬할 때는 Map(또는 일반 객체)을 인덱스로 활용하는 패턴을 기억해 두면 유용합니다.