[2.연결리스트] LinkedList, 재귀, LinkedListNode

1. 연결리스트란 ?

: 차례대로 연결된 노드를 표현해주는 자료구조

 

    1) 단방향 연결리스트 : 노드는 다음 노드를 가르킨다.

    2) 양방향 연결리스트 : 노드는 다음 노드와 이전 노드를 가르킨다.

: 특정 인덱스 접근시 상수시간에 접근 불가 (처음부터 ~K번까지 루프를 돌려야하기 때문)

: 따라서 시작지점에서 아이템 추가/삭제를 상수시간에 할 수 있는 특정 어플리케이션에서 유용하게 사용됨

 

 

 

2.  단방향 연결리스트 만들기

: LinkedList자료구조를 사용하지 않고 구현 > head의 노드주소를 참조하는 방법 사용

: 즉, 노드속 필드로 노드를 연결

class Node{
		Node next=null;
		int data;
		public Node(int d) {
			data=d;
		}
		void appendToTail(int d) {
			Node end=new Node(d);
			Node n=this;
			
			while(n.next!=null) {
				n=n.next;
			}
			n.next=end;
		}
	}

: 하지만 위의 경우 여러객체가 동시에 head를 참조하는경우 head 변경시 오류발생우려

  따라서 Node클래스를 포함하는 LinkedList클래스를 만드는 것을 권장 (해당클래스안에 head Node변수만 정의)

 

 

 

 

3. 연결리스트 삭제

: 양방향의 경우 n.next.prev=n.prev

: 단방향의 경우 n.next=n.prev

Node deleteNode(Node head, int d) {
		Node n=head;
		
		if(n.data==d) {
			return head.next; // head를 움직인다
		}
		
		while(n.next!=null) {
			if(n.next.data==d) {
				n.next=n.next.next;
				return head; // head는 변하지않는다
			}
			n=n.next;
		}
		return head;
	}

 

 

4. Runner기법

: 부가포인터기법

: 두개의 포인터 사용 > 한 포인터가 다른 포인터의 지정된 개수만큼 앞에 위치

: (e.g.) a1, a2, a3, ... b1, b2, b3, ... 의 연결리스트를 a1,b1,a2,b2, ... 순으로 정리하고싶은 경우(요소개수짝수가정)

  => Runner포인터를 Current포인터보다 2개 앞서게 하여 Runner가 끝까지 도달한경우 다시 정렬하는 방법

 

 

 

5. 재귀문제

: 연결리스트 관련 문제 중 상당수는 재귀호출에 의존 > 재귀적접근을 시도해봐라

: 재귀호출 깊이가 n인 경우, O(n)만큼의 공간 사용

: 재귀호출은 반복(iterator)형태로 구현가능하지만 반복이 조금더 복잡할 수 있다는 점을 기억!

 

 

 

6. LinkedListNode를 구현한 클래스 : 라이브러리

public class LinkedListNode {
	public LinkedListNode next, prev, last;
	public int data;
	
	public LinkedListNode() {
		// TODO Auto-generated constructor stub
	}
	
	public LinkedListNode(int d) {
		data=d;
	}
	
	public LinkedListNode(int d, LinkedListNode n, LinkedListNode p) {
		data=d;
		setNext(n);
		setPrevious(p);
	}
	
	public void setNext(LinkedListNode n) {
		next=n;
		if(this==last) {
			last=n;
		}
		if(n!=null&&n.prev!=this) {
			n.setPrevious(this);
		}
	}
	
	public void setPrevious(LinkedListNode p) {
		prev=p;
		if(p!=null&&p.next!=this) {
			p.setNext(this);
		}
	}
	
	public LinkedListNode clone() {
		LinkedListNode next2=null;
		if(next!=null) {
			next2=next.clone();
		}
		LinkedListNode head2=new LinkedListNode(data, next2, null);
		return head2;
	}

}