[인프런|12강] C로 배우는 자료구조 | 연결 리스트 (1)

연결 리스트 (1)

개념과 기본연산

 

- 리스트

기본적인 연산: 삽입(insert), 삭제(delete), 검색(search) 등

리스트를 구현하는 대표적인 두 가지 방법: 배열, 연결 리스트

 

- 배열

장점

랜덤 액세스가 가능하다. 어떤 위치이든 인덱스를 통해 접근 쉽다.

시작 주소 +  가고자 하는 곳의 위치(ex 4번째 칸이면 4) * 1칸의 크기(데이터 타입의 기본 바이트 )

 

단점

크기가 고정 -reallocation이 필요하다.

리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 한다.

 

- 연결 리스트

다른 데이터의 이동 없이 중간에 삽입이나 삭제가 가능하며, 길이의 제한이 없다.

하지만 랜덤 액세스가 불가능하다.

 

 

연결 리스트는 물리적으로 연속된 공간 데이터를 저장하지 않는다

노드는 데이터 필드와 링크 필드(주소) 두 개로 나뉘어 있어서 링크 필드(주소)에서 다음 노드(데이터 필드 + 링크 필드)를 가리키기만 하면 된다.

 

삽입과 삭제를 할떄에도 링크 필드에가리키고 있는 다음 노드의 주소를 변경해주는 것으로 삽입 삭제에 따른 순서의 변경을 적용한다. 배열의 경우 중간에 있는 데이터가 삽입 삭제되면 뒤에 있는 데이터를 다 이동시켜주어야 했지만 

연결 리스트는 중간에 연관되는 노드의 링크 필드 값을 바꿈으로써 간단하게 처리할 수 있다.

 

연결 리스트의 노드는 구조체를 이용하여 데이터 필드, 링크 필드 등의 개념을 구현한다.