리스트
데이터를 순서대로 나열한 자료구조이다.
-
선형 리스트
데이터가 배열처럼 연속하는 메모리 공간에 저장되어 순서를 갖는다. -
연결 리스트
데이터가 메모리 공간에 연속적으로 저장되어 있지 않더라도 각각의 데이터 안에 다음 데이터에 대한 정보를 갖고 있어 서로 연결 된다.
포인터로 연결 리스트 만들기
class Node<E>{
E data; // 데이터를 참조
Node<E> next; // 다음 노드를 참조
}데이터형 E는 임의의 클래스형이 허용됩니다. (사용하는 쪽에서 자유롭게 형을 지정할 수 있다.)
data의 자료형인 E가 참조형이다.
next를 뒤쪽 포인터라고 부른다. 뒤쪽 포인터 next에 넣어 두는 것은 다음 노드에 대한 참조이다.
꼬리 노드의 뒤쪽 포인터값은 널을 참조하도록 한다.
import java.util.Ccomparator;
public class LinkedList<E> {
// 노드
class Node<E> {
private E data; // 데이터
private Node<E> next; // 뒤쪽 포인터(다음 노드 참조)
// 생성자
Node(E data, Node<E> next) {
this.data=data;
this.next=next;
}
}
private Node<E> head; // 머리 포인터
private Node<E> crnt; // 선택 포인터
- 검생 메서드 search
주어진 조건을 만족하는 노드를 검색한다.
public E search(E obj, Comparator<? super E> c) {
Node<E> ptr = head; // 현재 스캔 중인 노드
while (ptr != null) {
if(c.compare(obj, ptr.data) == 0) {
crnt=ptr; // crnt 현재 선택한 노드를 가리킨다.
return ptr.data;
}
ptr = ptr.next; // 다음 노드를 선택
}
return null; // 검색 실패
}-
종료 조건
1) 검색 조건을 만족하는 노드를 찾지 못하고 꼬리 노드를 지나가기 직전인 경우
2) 검색 조건을 만족하는 노드를 찾은 경우 -
addFirst : 머리에 노드를 삽입하는 메서드
메서드는 리스트의 머리에 노드를 삽입한다.
public void addFirst(E obj) {
Node<E> ptr = head; // 삽입 전의 머리 노드
head = crnt = new Node<E>(obj, ptr);
}head에 선택 포인터 crnt를 생성한다.
obj가 되고 뒤쪽 포인터가 가리키는 곳은 ptr이 된다. 생성한 노드를 참조하도록 head를 업데이트 한다.
- addLast : 꼬리에 노드를 삽입하는 메서드
addLast 메서드는 리스트 꼬리에 노드를 삽입한다.
리스트가 비어 있는지 아닌지 (head==null)먼저 확인하고 경우에 따라 처리한다.
1) 리스트가 빈 경우 : 머리에 노드를 삽입한다. addFirst 메서드로 처리한다.
2) 리스트가 비어 있지 않은 경우 : 리스트 꼬리에 노드 G를 삽입한다.
public void addLast(E obj) {
if (head == null)
addFirst(obj); // 비어있다면 머리에 삽입
else { // 리스트 꼬리에 노드 G를 삽입한다.
Node<E> ptr=head;
while (ptr.next != null)
ptr=ptr.next;
ptr.next=crnt=new Node<E>(obj, null); //삽입할 노드 G를 생성한다.
}
}- removeFirst : 머리 노드를 삭제하는 메서드
머리 노드를 삭제한다.
public void removeFirst() {
if(head != null) // 리스트가 비어 있지 않으면
head=crnt=head.next; // 다음 노드를 가리킨다.
}- removeLast : 꼬리 노드를 삭제하는 메서드
메서드는 꼬리 노드를 삭제한다. 리스트에 노드가 몇 개 있는지 따라 처리한다.
1) 리스트에 노드가 1개만 있는 경우 : 머리 노드를 삭제하고, removeFirst 메서드로 처리한다.
2) 리스트에 노드가 2개 이상 있는 경우 : 리스트에서 꼬리 노드 F를 삭제한다.
public void removeLast() {
if (head != null) {
if (head.next == null) // 리스트에 노드가 1개만 있는 경우
removeFirst();
else { // 리스트에 노드가 2개 이상 있는 경우
Node<E> ptr=head; // 스캔 중인 노드
Node<E> pre=head; // 스캔 중인 노드의 앞쪽 노드
while (ptr.next != null) {
pre=ptr;
ptr=ptr.next;
}
pre.next=null; //pre는 삭제 후의 꼬리 노드
crnt=pre;
}
}
}1) addLast메서드인 3과 거의 같다.
head.next == null
removeFirst();
else 리스트에 노드가 2개 이상 있는 경우
Node ptr=head;
Node pre=head; // 스캔 중인 노드의 앞쪽 노드
배열 커서로 연결 리스트
원형 이중 연결 리스트
공부 기록