데이터 구조 및 알고리즘 - 단일 연결 목록

단일 연결 리스트는 헤드(첫 번째 노드)에서 테일(끝 또는 마지막 노드)까지 한 방향으로 데이터를 읽을 수 있는 연결 리스트 유형입니다. 단일 연결 목록은 배열과 유사하지만 배열의 세 번째 항목에 액세스해야 하는 경우 연결 목록에서 세 번째 항목에 도달할 때까지 각 노드를 통과해야 하는 위치에 직접 액세스할 수 있다는 점에서 다릅니다. 마디. 나는 메모리와 이러한 데이터 구조가 실제로 메모리에 어떻게 저장되는지에 대해 너무 많이 이해하지 못하지만 내가 아는 것을 설명하려고 노력할 것입니다. 모든 배열에는 연결 목록에서 다음 노드에 대한 포인터와 함께 사용 가능한 메모리 슬롯에 저장할 수 있는 연속 메모리 슬롯이 필요합니다.

따라서 메모리가 사용되는 한 연결된 목록은 배열보다 훨씬 더 메모리 효율적입니다. 연결된 목록에서 노드를 추가하고 제거하면 노드에 대해 새 포인터를 덮어쓰고 설정합니다. 배열에서 삽입 및 제거할 때 실제로 삽입 또는 삭제 후 모든 요소를 ​​이동하고 이동해야 합니다. 배열 끝에 추가하는 것 외에 성능 면에서 연결 목록을 능가하는 유일한 시간인 것 같습니다. 이제 이 사실을 알게 되면서 연결된 목록이 메모리에서 더 효율적인 이유와 사용 사례에 따라 어레이(현재 매일/항상 사용하는)보다 더 나은 성능을 보이는 이유를 실제로 알 수 있습니다. 가까운 장래에 나의 목표는 이러한 새로운 학습 데이터 구조를 내 코드 베이스에 실제로 구현하기 시작하는 것입니다. 그것이 필요합니까, 아마도 그렇지 않을 것입니다. 아무도 신경 쓰지 않을 것입니다. 아니요(저는 현재 팀에서 유일한 개발자로 일하고 있습니다.....), 하지만 그것이 저를 더 잘 이해하고 학습 경로를 계속하는 데 도움이 될 것입니다, 예!!! !

나는 개인적으로 인터뷰에서 이것을 본 적이 없지만 누군가가 당신의 경력의 어느 시점에서 당신에게 물어볼 더 일반적이고 낮은 수준의 질문 중 하나는 단일 연결 목록을 뒤집는 것이라고 생각합니다. 왜 중요 함? 내 말은 그것이 내가 할 수 있는 배열Array.reverse()이고 bam 나를 보세요. 내가 수집한 아이디어는 가장 간단한 데이터 구조를 얼마나 잘 알고 있는지, 모든 노드와 값을 역순으로 순회하고 저장할 수 있는지입니다. 그러니 해보자!!!!!!!!!

나는 더 잘 이해하기 위해 javascript Singly Linked List 데이터 구조를 구축했습니다. 이것은 시간이 지남에 따라 만들게 될 다른 모든 데이터 구조와 함께 여기에서 찾을 수 있습니다. SinglyLinkedList . 따라서 repo를 보면 위의 명령문을 처리하는 역방향 함수를 추가했지만 여기에 다시 입력할 것임을 알 수 있습니다. 반복적으로나 재귀적으로 할 수 있다는 것을 알고 있습니다. 저는 표준 반복을 다룰 것입니다. github에서 제 수업을 보면 for 루프로 수행하지만 여기서는 while 루프로 변경하겠습니다.

function reverse(list) {
    let node = list.head;
    let previous = null;
    let next = null;
    while(node) {
        next = node.next;
        node.next = previous;
        previous = node;
        node = next;
    }
    return list;
}

따라서 이 중 일부 또는 일부가 개발자로서의 성장에 도움이 되기를 바랍니다. 특히 이 특정 주제를 다룰 때 매우 짧은 시간에 많은 학습을 짜내려고 노력한다고 말할 것입니다. 시간을 갖고 무슨 일이 일어나고 있는지 이해하려고 노력하십시오. 나는 내 조언을 받아들이지 않는 시간의 절반을 말하고 싶으므로 이 여정이 어떻게 끝나는지 다시 보게 될 것입니다.