연결리스트

연결리스트는 1955~1956년에 랜드 연구소에서 앨런 뉴웰, 클리프 셔, 허버트 A. 사이먼이 만든 정보처리를 위한 자료구조 입니다.

연결리스트는 배열과 달리 각각의 데이터는 메모리 상에 산재해 있지만 데이터들간에 서로의 위치를 기억하는 포인터를 지니고 있습니다.

연결리스트의 종류는 3가지로 각각 단일 연결리스트, 이중 연결 리스트, 원형 연결 리스트가 존재합니다.

단일 연결 리스트는 헤드노드(첫노드)를 시작으로 각 노드가 자신의 다음노드의 위치를 기억하되

일방향으로만 진행되는 연결리스트 입니다. 

이중 연결 리스트는 단일 연결에 추가로 자신의 전 노드의 정보또한 가지고 있는 노드 입니다.

원형 연결리스트는 꼬리노드가 헤드노드의 정보를 가지고 있기에 원형순회가 가능한 연결 리스트 구조입니다.

연결리스트의 장점은 배열과 비교할때 드러납니다.

배열의 경우 데이터 관리에서 접근성이 좋지만 데이터의 추가가 이뤄질때 그만큼 뒤의 데이터들이 밀려나며 발생하는 자원의 소모가 

많습니다.

하지만 연결리스트는 추가를 원하는 지점에 있는 노드들의 연결을(포인터) 수정하고 그 사이에 새 노드를 끼워넣기만 하면 됩니다.

하지만 단점도 존재하는데, 

연결리스트는 그 특성상 순차적으로 탐색을 진행해서 접근해야 합니다.

그러다보니 데이터를 읽고 순회하는데 드는 시간은 연결리스트의 크기에 정비례 합니다.

연결리스트 객체의 구조는 다음과 같이 간략화가 가능합니다.

노드(노드가 가진 데이터와 다음 노드를 가르킴)

리스트(리스트의 현재 크기와 시작과 끝점을 기억함)

리스트 추가 & 삭제