単一接続リスト

ポインタを使用した接続リストの作成

import java.util.Comparator; //연결 리스트 클래스 

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; //선택 노드; 검색, 삭제 용도 
    private int size; //요소 개수(=연결된 노드의 개수) 
}

作成者:Nodeの作成者はそのフィールドに引数として渡されるデータを設定し、next

ナビゲーションリスト

   	//탐색하기
	private Node<E> search(int index){
		if(index<0 || index>=size) { //인덱스 범위 밖인 경우 오류 
			throw new IndexOutOfBoundsException();
		}
		
		Node<E> x = head;
		
		for(int i=0; i<index; i++) {
			x = x.next;
		}
		return x;
	}

リストの挿入

	//머리에 노드 삽입 
	public void addFirst(E obj) {
		Node<E> ptr = head; //머리 노드에 대한 포인터 -> ptr 
		head = crnt = new Node<E>(obj, ptr); 
		//삽입할 노드 생성, 뒤쪽 포인터 ptr, 생성한 노드를 참조하도록 head 업데이
	}
	
	//꼬리에 노드 삽입 
	public void addLast(E obj) {
		if(head==null) //리스트가 비어 있으면 
			addFirst(obj); //머리에 삽입 
		else {
			Node<E> ptr = head;
			while(ptr.next != null) //꼬리 노드 찾기 -> 처음부터 차례로 스캔 
				ptr = ptr.next;
			ptr.next = crnt = new Node<E>(obj, null);
		}
	}
  
    //중간에 노드 삽입 
	public void add(int index, E obj) {
		if(index<0 || index>=size) {
			throw new IndexOutOfBoundsException();
		}
		
		//0번째 인덱스(맨앞)에 추가
		if(index == 0) {
			addFirst(obj);
			return;
		}
		
		//마지막 인덱스 추가 
		if(index == size-1) {
			addLast(obj);
			return;
		}
		
		Node<E> newNode = new Node<E>(obj, null);
		Node<E> prevNode = search(index-1);
		Node<E> nextNode = prevNode.next;
		
		/*연결된 노드와 노드 사이를 끊기 
  -> 선행 노드의 끝은 null로, 추가한 노드의 끝은 후행 노드의 링크를 넣어준다.*/
		prevNode.next = null;
		prevNode.next = newNode;
		newNode.next = nextNode;
		size++;
	}

リストの削除

	//머리 노드 삭제
	public void removeFirst() {
		if (head != null) //리스트가 비어 있지 않으면 
			head = crnt = head.next;
	}
	
	//꼬리 노드 삭제 
	public void removeLast() {
		if(head != null) {
			if(head.next == null) //노드가 하나만 있으면 머리 노드 삭제 
				removeFirst();
			else {
				Node<E> ptr = head; //스캔 중인 노드 
				Node<E> pre = head; // 스캔 중인 노드의 앞쪽 노드 
				
				while(ptr.next != null) { //ptr -> 꼬리 노드, pre -> 꼬리로부터 두 번째 노드 
					pre = ptr;
					ptr = ptr.next; 
				}
				pre.next = null;
				crnt = pre;
			}
		}
	}
	
	//중간 노드 삭제 
	public void remove(Node p) {
		if(head != null) {
			if(p==head) //p가 머리 노드면 머리 노드 삭제 
				removeFirst();
			else {
				Node<E> ptr = head;
				
				while(ptr.next != p) {
					ptr = ptr.next;
					if(ptr == null) return ;
				}
				ptr.next = p.next;
				crnt = ptr;
			}
		}
	}
	
	//선택 노드 삭제
	public void removeCurrentNode() {
		remove(crnt);
	}
	
	//모든 모드 삭제 
	public void clear() {
		while(head != null)
			removeFirst();
		crnt = null;
	}

追加

	//선택 노드를 하나 뒤쪽으로 이동 
	public boolean next() {
		if(crnt == null || crnt.next == null) //이동 불가 
			return false; 
		crnt = crnt.next;
		return true;
	}
	
	//선택 노드 출력 
	public void printCurrentNode() {
		if(crnt == null)
			System.out.println("선택한 노드가 없습니다.");
		else
			System.out.println(crnt.data);
	}
	
	//모든 노드를 출력 
	public void dump() {
		Node<E> ptr = head;
		
		while(ptr != null) {
			System.out.println(ptr.data);
			ptr = ptr.next;
		}
	}