선형리스트란? / 포인터로 연결 리스트 만들기

1. 선형리스트(linear list)란?

- 리스트는 데이터를 순서대로 나열해 놓은 자료구조

- 리스트의 데이터는 노드(node) 또는 요소(element)라고 하며 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있음.

- 연결 리스트(linked list)라고도 부름.

- 처음과 끝에 있는 노드는 각각 머리노드(head node), 꼬리 노드(tail node)라고 함.

- 앞에있는 노드를 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드를 다음 노드(successor node)라고함.

선형 리스트의 문제점

1) 쌓이는 데이터의 크기를 미리 알야아함

2) 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 못함.

---

2. 포인터로 연결 리스트 만들기

데이터용 필드인 data와는 별도로 자기 자신과 같은 클래스형의 인스턴스를 참조하기 위한 참조용 필드 next를 가집니다. 일반적으로 이런 클래스 구조를 자기 참조(self-referential)형이라고 합니다.

- 노드 클래스 생성 코드 및 머리 노드 삽입

- 노드 클래스 Node<E>

 data : 데이터를 가리킵니다.

 next : 다음 노드를 가리키는 포인터입니다.

 생성자 : Node<E>의 생성자는 인수로 전달받은 data, next를 해당 필드에 설정합니다.

- 연결 리스트 클래스 LinkedList<E>

 head : 머리 노드를 가리킵니다.

 crnt : 현재 선택한 노드를 가리킵니다. "검색"한 노드를 선택하고 "삭제"하는 등의 용도로 사용됩니다.

---

---

- 이번에는 꼬리노드에 추가하는 코드입니다.

---

- 검색을 수행하는 search 메서드

여기서 Comparator<? super E> 가 무엇인지 검색해보았습니다.

Comparator는 int compareTo(E o1, E o2)가 있는데요. 이 타입 E 또는 E의 조상들 만일 class Student extends Person {} 이렇게 정의 되어 있고 타입 E가 Student라면 E의 조상은 Person, Object가 되겠죠. public TreeSet(Comparator<? super E> comparator) { 결국 다입 E가 Student라면 위의 문장은 아래의 문장들중 하나가 가능하다는 얘기입니다. public TreeSet(Comparator<Student> comparator) { public TreeSet(Comparator<Person> comparator) { public TreeSet(Comparator<Object> comparator) { 보통은 아래와 같이 하겠지만... 조상타입도 가능하게 허용한다는 뜻입니다. public TreeSet(Comparator<Student> comparator) {

E : Element -> 요소, 원소 ? : 와일드카드 -> 사용 가능한 타입의 범위 <?> : Object -> 모든 타입 가능 <? super E> : Object >= 유효한 E 범위 >= E <? extends E> : E >= 유효한 E 범위 >= E를 상속 받은 클래스나 구현 받은 인터페이스

출처 : https://cafe.naver.com/javachobostudy/73588

그외에 나머지는 코드를 보시면 이해되실겁니다.

메서드	메서드를 실행한 후 선택 노드(crnt)가 가리키는 노드
생성자	null
Search	검색에 성공하면 검색한 노드
addFirst	삽입한 머리 노드
addLast	삽입한 꼬리 노드
removeFirst	삭제 후 머리 노드(리스트가 비어있으면 null)
removeLast	삭제 후 꼬리 노드(리스트가 비어있으면 null)
remove	삭제한 노드의 앞쪽 노드
removeCurrentNode	삭제한 노드의 앞쪽 노드
clear	null
next	옮긴 후 선택 노드
PrintCurrentNode	업데이트하지 않음
dump	업데이트하지 않음

- LinkedList_09_01

- LinkedListTester_09_01