리스트 (List)
- 리스트(list) 또는 선형 리스트(linear list)는 자료들이 차례대로 나열된 선형 자료구조로,
각 자료는 순서 또는 위치(position)을 가진다. - 어떤 위치에서도 새로운 요소를 삽입할 수 있다.
- 어느 위치에 요소를 삽입하려면 이후 모든 자료가 1칸씩 뒤로 밀린다.
- 마찬가지로 요소를 삭제하면, 이후의 모든 요소의 위치가 변경된다.
- 스택이나 큐, 덱에서도 자료들을 일렬로 저장하지만 자료 접근은 전단이나 후단으로 제한되어있지만,
리스트는 이러한 제한이 없다! → 가장 활용이 자유로운 선형자료구조
리스트(List vs Set(집합))
- 리스트에서는 순서가 있지만 집합은 원소 사이에 순서가 없다.
- 집합은 원소의 중복을 허용하지 않는다.
- 집합은 원소 사이에 순서의 개념이 없으므로, 선형 자료구조라 볼 수 없다.
리스트의 연산
- insert(pos, e): pos 위치에 새로운 요소 e를 삽입
- delete(pos): pos 위치에 있는 요소를 꺼내서 반환
- getEntry(pos): pos 위치에 있는 요소를 삭제하지 않고 반환
- isEmpty(): 리스트가 비어있으면 True, 아니면 False 반환
- isFull(): 리스트가 가득차있으면 True, 아니면 False 반환
- size(): 리스트에 들어있는 전체 요소의 수를 반환
연결된 구조 (Linked Structure)
메모리에 흩어져있는 요소들을 링크로 연결해 하나로 관리하는 것
연결 리스트 (Linked List)
자료들을 링크를 통해 일렬로 나열할 수 있는 연결된 구조
노드 (Node)
연결된 구조에서 하나의 상자
연결 리스트의 구조
노드(node)
연결 리스트에서 하나의 노드는 하나의 데이터와 함께 하나 이상의 링크를 갖는다.
링크는 다른 노드를 가리키는(다른 노드의 주소를 저장하는) 변수이다.
헤드 포인터(head pointer)
연결 리스트는 시작 노드만 알면 링크로 매달려있는 모든 노드에 순차적으로 접근 가능한데,
이 노드를 보통 머리 노드(head node)라고 부른다.
머리 노드의 주소를 저장하는 변수를 헤드 포인터(head pointer)라고 부른다.
마지막 노드를 보통 꼬리 노드(tail node)라고 부른다.
꼬리 노드의 링크를 처리하는 방법에 따라 단순 연결과 원형 연결로 구분된다.
연결 리스트의 종류
단순 연결 리스트(singly linked list)
하나의 방향으로만 연결된 리스트.
노드의 하나의 링크를 갖으며, 다음 노드의 주소가 저장된다.
꼬리 노드의 링크는 마지막 노드라는 것을 나타내기 위해 None을 갖기고 약속되어있다.
원형 연결 리스트(circular linked list)
꼬리 노드의 링크가 None이 아니라 다시 머리 노드를 가리키도록 하는것.
이러한 원형 연결 구조에서는 어떤 노드에서 시작해도 다른 모든 노드를 찾아갈 수 있지만,
노드들을 순서대로 방문할때 종료 조건 처리에 조심해야한다.
이중 연결 리스트(doubly linked list)
하나의 노드가 이전 노드와 다음 노드의 링크를 모두 갖도록 설계되어있다.
2개의 링크를 갖는데, 하나는 이전 노드(previous node)를, 다른 하나는 다음 노드(next node)를 가리키도록 하는 것이다.
