[윤성우의 열혈 자료구조]단순 연결리스트(Singly linked list) - 자바(Java) 구현

단순 연결리스트

• head
  • 처음 연결리스트를 가리키기 위한 것

• tail
  • 마지막 연결리스트를 가리키기 위한 것(없는 경우도 있음)

• cur
  • 참조 및 조회를 위한 것

 

새 노드의 추가 위치에 따른 장점과 단점

• 새 노드를 연결 리스트의 머리에 추가하는 경우
  • 장점 : 포인터 변수 tail이 불필요하다.(관리 포인트가 늘어난다.)
  • 단점 : 저장된 순서를 유지하지 않는다.

• 새 노드를 연결리스트의 꼬리에 추가하는 경우
  • 장점 : 저장된 순서가 유지된다.
  • 포인터 변수 tail이 필요하다.(관리 포인트가 줄어든다.)

더미노드 기반 연결리스트

• 연결리스트 등록 및 삭제 과정에서 동작의 일관성을 유지할 수 있다.(관리 포인트를 줄이고 에러발생 확률을 낮춘다.
  • 코드를 간결하게 구성할 수 있다.(처리과정을 하나로 묶을 수 있다.)
  • 더미노드를 사용하지 않은 경우, head에 연결리스트를 등록하는 과정과 그 이후의 연결리스트를 등록하는 과정이 분리되어서 동작한다.(즉 동일한 연결리스트를 처리하지만 처리과정이 다르다.)

정렬 기능이 추가된 리스트 자료구조의 추상 자료형(ADT)

	void LInsert(T data); //리스트에 데이터 저장

	boolean LFirst(); // 첫 번째 데이터부터 참조

	boolean LNext(); // 두 번째 이후 데이터 참조

	T LRemove(); // 참조한 데이터 삭제

	int LCount(); // 저장되어 있는 데이터의 수를 반환

	void SetSortRule(Comparator<T> comp); // 정렬의 기준 설정

 

단순 연결리스트

public class SimpleLinkedList2<T> {
	
	//노드를 표현한 클래스
	private class Node{
		private T data;
		private Node nextLink;
		
		private Node() {
			this.data = null;
			this.nextLink = null;
		}
		private Node(T data) {
			this.data = data;
			this.nextLink = null;
		}
	}

	private Node head;					//더미 노드를 가리키는 멤버
	private Node cur;					//참조 및 삭제를 돕는 멤버
	private Node before;				//삭제를 돕는 멤버
	private int numOfData;				//저장된 데이터의 수를 기록하기 위한 멤버
	private Comparator<T> comp;			//정렬의 기준을 등록하기 위한 멤버
	private T data;
	
	public SimpleLinkedList2() {
		this.head = new Node(); //더미노드
		this.head.nextLink = null;
		this.comp = null;
		this.numOfData = 0;
	}

	/**
	 * 리스트에 데이터 저장
	 * @param data
	 */
	public void LInsert(T data) {
		if(comp == null) { //정렬기준이 마련되지 않았다면,
			FInsert(data);	// 머리에 노드를 추가
		} else { //정렬기준이 마련되었다면,
			SInsert(data); //정렬기준에 근거하여 노드를 추가
		}
	}
	
	/**
	 * 정렬이 기준이 마련되지 않았을 경우 추가
	 * @param data
	 */
	public void FInsert(T data) {
		Node newNode = new Node(data);
		newNode.nextLink = head.nextLink;
		head.nextLink = newNode;		 
		numOfData++;
	}
	
	/**
	 * 정렬 기준이 마련된 경우 추가
	 * @param data
	 */
	public void SInsert(T data) {
		Node newNode = new Node(data);
		Node pred = head;	//추가를 돕는 멤버 
		newNode.data = data;
		
		while(pred.nextLink != null && comp.compare(data, pred.nextLink.data) != 0) {
			pred = pred.nextLink;
		}
		newNode.nextLink = pred.nextLink;
		pred.nextLink = newNode;
		numOfData++;
	} 
	
	/**
	 * 저장된 첫 번째 데이터 탐색 및 탐색 초기화 용도
	 * @return
	 */
	public boolean LFirst() {
		if (head.nextLink == null) {
			return false;
		}
		before = head;			//더미 노드를 가리키게 함
		cur = head.nextLink;	//첫 번째 노드를 가리키게 함
		data = cur.data;	//첫 번째 노드의 데이터 전달
		return true;
	}
	
	/**
	 * 두 번째 이후 데이터 참조
	 * @return
	 */
	public boolean LNext() {
		if (cur.nextLink == null) {
			return false;
		}
		before = cur;		 //이전 노드를 가리키는 before을 한칸 우측 이동
		cur = cur.nextLink;	 //현재 노드를 가리키는 cur을 한칸 우측 이동
		data = cur.data;
		return true;
	}
	
	/**
	 * 참조한 데이터 삭제
	 * 두 번 이상 호출 되면 안됨. 한 번 호출 후 LNext() 또는 LFirst() 호출 후 사용가능 
	 * @return
	 */
	public T LRemove() {
		Node rpos = cur;
		T rdata = rpos.data;
		before.nextLink = cur.nextLink;
		cur = before;		//cur은 삭제 후 재조정의 과정을 거쳐야 하지만 before는 LFirst 또는 LNext 호출 시 재설정되므로 재조정의 과정이 불필요
		numOfData--;
		return rdata;
	}
	
	/**
	 * 저장되어 있는 데이터의 수를 반환
	 * @return
	 */
	public int LCount() {
		return numOfData;
	}
	
	/**
	 * 정렬 기준 설정
	 * @param comp
	 */
	public void SetSortRule(Comparator<T> comp) {
		this.comp = comp;
	}
	
	public static void main(String[] args) {
		SimpleLinkedList2<Integer> simpleLinkedList2 = new SimpleLinkedList2<>();
		simpleLinkedList2.SetSortRule(
				(d1, d2) -> {
					if(d1 < d2)
						return 0;    // d1이 정렬 순서상 앞선다.(head 쪽에 가깝다)
					else
						return 1;
				}
		);
		
		// 5개의 데이터 저장  ///////////////
		simpleLinkedList2.LInsert(11);
		simpleLinkedList2.LInsert(11);
		simpleLinkedList2.LInsert(22);
		simpleLinkedList2.LInsert(22);
		simpleLinkedList2.LInsert(33);
		
		// 저장된 데이터의 전체 출력 ////////////
		System.out.printf("현재 데이터의 수: %d \n", simpleLinkedList2.LCount());
		
		if(simpleLinkedList2.LFirst())
		{
			System.out.printf("%d ", simpleLinkedList2.data);
			
			while(simpleLinkedList2.LNext()) 
				System.out.printf("%d ", simpleLinkedList2.data);
		}
		System.out.printf("\n\n");

		// 숫자 22을 검색하여 모두 삭제 ////////////
		if(simpleLinkedList2.LFirst())
		{
			if(simpleLinkedList2.data == 22)
				simpleLinkedList2.LRemove();
			
			while(simpleLinkedList2.LNext())
			{
				if(simpleLinkedList2.data == 22)
					simpleLinkedList2.LRemove();
			}
		}

		// 삭제 후 저장된 데이터 전체 출력 ////////////
		System.out.printf("현재 데이터의 수: %d \n", simpleLinkedList2.LCount());

		if(simpleLinkedList2.LFirst())
		{
			System.out.printf("%d ", simpleLinkedList2.data);
			
			while(simpleLinkedList2.LNext())
				System.out.printf("%d ", simpleLinkedList2.data);
		}
		System.out.printf("\n\n");
		
		// 데이터 등록 후 저장된 데이터 전체 출력 ////////////
		simpleLinkedList2.LInsert(15);
		simpleLinkedList2.LInsert(55);
		simpleLinkedList2.LInsert(32);
		System.out.printf("현재 데이터의 수: %d \n", simpleLinkedList2.LCount());
		if(simpleLinkedList2.LFirst()) {
			System.out.printf("%d ", simpleLinkedList2.data);
			
			while(simpleLinkedList2.LNext())
				System.out.printf("%d ", simpleLinkedList2.data);
		}
	}
}

 

연결 리스트의 단점

• 데이터 참조가 어렵다. 특정 데이터를 찾기 위해 많은 연결 리스트를 확인해야 한다. 최악의 경우 모든 연결리스트를 확인해야 한다.

 

연결 리스트의 장점

• 배열기반 리스트와 다르게 리스트의 길이가 초기에 결정될 필요가 없다.(필요할 때마다 동적으로 생성)

• 삭제의 과정에서 불필요한 데이터의 이동(복사)이 발생하지 않는다. 삭제한 데이터와 관련있는 연결리스트만 조작한다.

---

[참고자료]

윤성우의 열혈 자료구조