[자료구조] Linked list (연결 리스트)

[자료구조] Linked list (연결 리스트)

친한 형에게 자료구조에 대해서 알아두면 좋을 거라는 이야기를 들었지만, 눈앞의 업무에 열중하면서 뒤로만 미루다가 최근 자료구조에 대한 설명 영상과 글을 보게 되면서 다시 중요성을 느끼게 되어 그때그때 조금씩 추가하면서 정리를 해보려고 합니다.ㅎㅎ

개념 정리

자료들이 반드시 연속적으로 배열되어있지 않아도 노드 포인터 부분을 이용하여 서로 연결된 구조

구조

노드(Node) = 데이터 필드(Data Field) + 링크 필드(Link Field)

헤드 포인터(Head Pointer) : 첫 번째 노드를 가리키는 포인터

개념 비교

Linked List(연결 리스트) : 데이터가 들어올 때마다 동적으로 메모리를 할당하는 자료구조

array List(배열 리스트) : 연속된 메모리 공간에 할당되는 자료구조 (추가적으로 소모되는 메모리 양 효율에 좋음)

Linked List(연결 리스트) : 자료들을 연속적으로 배열시키지 않고 임의의 기억공간에 기억시키지만, 자료 순서에 따라

노드의 포인터 부분을 이용하여 연결시킨 자료 구조 (노드 부분에 다음 노드를 가리키는

노드 포인트가 포함되어 있다)

Linear List(선형 리스트) : 배열과 같이 연속되는 기억 장소에 저장되는 리스트

종류

Input이 올 때마다 조그마한 저장 공간인 노드를 만들게 되고 노드 안에는 데이터를 저장할 수 있는 데이터 필드와 다음 노드를 알려주는 링크 필드가 있는데 링크의 변수 생김새를 보고 종류를 구분할 수 있습니다.

Singly Linked List : 단방향, 노드 안에 링크가 1개이다. Double Linked List : 양방향, 노드안에 링크가 2개이다. Circular Linked List : 마지막 노드가 첫 번째 노드를 가리켜서 계속 회전할 수 있게 만들어진 리스트이다.

장점

Input 사이즈를 모를 때, 메모리 할당 효율이 좋다. 데이터 추가와 삭제하기 쉽다.

단점

접근 속도가 느리다. 기억 장소 이용 효율이 안 좋다. (노드 포인트 정보를 추가해야 하기 때문)

from http://minisiri.tistory.com/4 by ccl(A) rewrite - 2021-10-29 18:26:37