[자료구조] Singly LinkedList

Singly LinkedList

Node라는 객체를 단방향으로 하나의 체인처럼 연결한 리스트

---

Node

 

Node는 사용자가 저장할 data와 다음에 연결할 노드를 가리키는 reference를 담고 있다

위와 같은 노드들이 아래과 같이 여러개 연결되어있는 것을 LinkedList라고 한다

---

 

 

또한 단방향으로 연결되어있을 경우 Singly LinkedList라고 한다

조회 성능이 좋진 않지만 삽입/삭제 시 링크만 바꿔주면 되기 때문에 효율적이다.

---

Singly LinkedList Implement in JAVA

Node.java

 

class Node<E> {
	E data;
	Node<E> next;
	
	Node(E data){
		this.data = data;
		this.next = null;
	}
}

 

List.java

 

add() method

1. addFirst(E value)

첫번째 위치에 요소 추가

addFirst(E value)

 

2. add(E value) & addLast(E value)

마지막 위치에 요소 추가

add(E value) & addLast(E value)

 

3. add(int index, E value)

특정 위치에 요소 추가

add(int index, E value)

 

remove() method

1. remove()

첫번째 요소 제거

remove()

 

2. remove(int index)

특정 위치의 요소 제거

remove(int index)

 

3. remove(Object value)

특정 요소 제거

remove(Object value)

 

---

public interface List<E> {
	
	/**
	 * 요소 추가 
	 * @param value
	 * @return 리스트에 이미 중복되는 요소가 있을 경우 false
	 * 		   없을 경우 true 반환 
	 */
	boolean add(E value);
	
	/**
	 * 특정 위치에 요소 추가 
	 * @param index
	 * @param value
	 * @return 리스트에 이미 중복되는 요소가 있을 경우 false
	 * 		   없을 경우 true 반환 
	 */
	void add(int index, E value);
	
	/**
	 * 특정 요소 삭제 
	 * @param value
	 * @return 삭제된 요소 반환 
	 */
	boolean remove(Object value);

	/**
	 * 특정 위치에 요소 삭제 
	 * @param index
	 * @return 삭제된 요소 반환 
	 */
	E remove(int index);

	/**
	 * 특정 위치에 요소 반환 
	 * @param index
	 * @return 조회된 요소 반환 
	 */
	E get(int index);

	/**
	 * 특정 위치의 요소를 새 요소로 대체
	 * @param index
	 * @param value
	 */
	void set(int index, E value);

	/**
	 * 요소 인덱스 반환 
	 * @param value
	 * @return 요소 인덱스 
	 */
	int indexOf(Object value);

	/**
	 * 특정 요소 존재 여부 반환 
	 * @param value
	 * @return 리스트에 특정 요소가 존재할 경우 true 
	 * 		   존재하지 않을 경우 false 반환  
	 */
	boolean contains(Object value);

	/**
	 * 리스트에 있는 요소 개수 반환  
	 * @return size  
	 */
	int size();

	/**
	 * 리스트에 있는 요소 개수 반환  
	 * @return 리스트에 요소가 없을 경우 true
	 * 	 	   있을 경우 false 반환   
	 */
	boolean isEmpty();

	/**
	 * 리스트에 있는 요소 전체 삭제 
	 */
	void clear();
}

 

SLinkedList.java

 

import java.util.NoSuchElementException;

class SLinkedList<E> implements List<E> {
	/*	리스트의 첫 노드	*/
	private Node<E> head;
	/*	리스트의 마지막 노드	*/
	private Node<E> tail;
	/*	리스트의 요소 개수	*/
	private int size; 
	
	public SLinkedList() {
		this.head = null;
		this.tail = null;
		this.size = 0;
	}
	
	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 value) {
		// 1. 새 노드 생성 
		Node<E> newNode = new Node<E>(value);
		// 2. 새 노드의 다음 노드로 head 노드 연결 
		newNode.next = head;
		// 3. 새 노드를 head 노드로 update 
		head = newNode;
		size ++;
		
		// 4. 새 노드가 첫번째 노드일 경우 마지막 노드로 저장 
		if(head.next == null) {
			tail = head;
		}
	}
	
	public void addLast(E value) {
		// 1. 새 노드 생성 
		Node<E> newNode = new Node<E>(value);
		// 2. 처음 넣는 노드일 경우 addFirst로 추가
		if(size == 0) {
			addFirst(value);
			return;
		}
		
		// 3. 마지막 노드의 다음 노드가 새 노드를 가리키도록 함
		tail.next = newNode;
		// 4.새 노드를 tail 노드로 update
		tail = newNode;
		size++;
	}
	
	@Override
	public boolean add(E value) {
		addLast(value);
		return true;
	}

	@Override
	public void add(int index, E value) {
		// 1. 삽입 위치에 따라 함수 처리 
		if(index > size || index < 0) {
			throw new IndexOutOfBoundsException();
		}else if(index == 0) {
			addFirst(value);
			return;
		}else if(index == size) {
			addLast(value);
			return;
		}
		
		// 2. 삽입 이전/이후 노드 조회 
		Node<E> prevNode = search(index - 1);
		Node<E> nextNode = prevNode.next;
		Node<E> newNode = new Node<E>(value);
		
		// 3. 삽입 이전노드의 다음노드를 초기화한 후 새 노드를 가리키도록 함 
		prevNode.next = null;
		prevNode.next = newNode;
		
		// 4. 새 노드가 삽입 이후 노드를 가리키도록 함 
		newNode.next = nextNode;
		size++;
	}
	
	public E remove() {
		// 1. 삭제할 head 노드 조회 
		Node<E> headNode = head;
		
		if(headNode == null) {
			throw new NoSuchElementException();
		}
		
		// 2. 반환할 head 노드 조회 
		E element = headNode.data;
		
		// 3. 새 head 노드로 설정할 현재 head 다음 노드 조회 
		Node<E> nextNode = head.next;
		
		// 4. head 노드 데이터 초기화 
		head.data = null;
		head.next = null;
		
		// 5. 새 head 노드를 다음 노드로 update 
		head = nextNode;
		size--;
		
		// 6. 리스트에 요소가 없을 경우 tail 초기화 
		if(size == 0) {
			tail = null;
		}
		return element;
	}

	@Override
	public boolean remove(Object value) {
		Node<E> prevNode = head;
		Node<E> x = head;	// 삭제 대상 노드 
		boolean hasValue = false;
		
		// 1. value와 일치하는 노드 조회 
		while(x != null) {
			if(value.equals(x.data)) {
				hasValue = true;
				break;
			}
			prevNode = x;
			x = x.next;
		}
		
		// 2. 일치하는 요소가 있을 경우 
		if(hasValue) {
			// 삭제하려는 노드가 head일 경우 기존 remove() 사용 
			if(x.equals(head)) {
				remove();
			}else {
				// 이전노드와 삭제하려는 노드의 다음 노드를 연결 
				prevNode.next = x.next;
				
				x.data = null;
				x.next = null;
				size--;
			}
		}
		return hasValue;
	}

	@Override
	public E remove(int index) {
		if(index < 0 || index >= size) {
			throw new IndexOutOfBoundsException();
		}else if(index == 0) {
			return remove();
		}
		
		// 1. 삭제 이전/이후 노드 조회 
		Node<E> prevNode = search(index - 1);
		Node<E> removedNode = prevNode.next;
		Node<E> nextNode = removedNode.next;
		
		// 2. 반환할 삭제 노드 데이터 조회 
		E element = removedNode.data;
		
		// 3. 삭제 노드 데이터 초기화 
		removedNode.next = null;
		removedNode.data = null;
		
		// 4. 삭제 노드 이전과 이후 노드 연결 
		prevNode.next = nextNode;
		size--;
		
		return element;
	}

	@Override
	public E get(int index) {
		return search(index).data;
	}

	@Override
	public void set(int index, E value) {
		Node<E> replaceNode = search(index);
		replaceNode.data = null;
		replaceNode.data = value;
	}

	@Override
	public int indexOf(Object value) {
		int index = 0;
		
		for(Node<E> x = head; x != null; x = x.next) {
			if(value.equals(x.data)) {
				return index;
			}
			index++;
		}
		// 요소를 찾지 못했을 경우 -1 반환 
		return -1;
	}

	@Override
	public boolean contains(Object value) {
		return indexOf(value) >= 0;
	}

	@Override
	public int size() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public void clear() {
		for(Node<E> x = head; x != null;) {
			Node<E> nextNode = x.next;
			
			x.data = null;
			x.next = null;
			x = nextNode;
		}
		head = tail = null;
		size = 0;
	}
}

 

 

---

reference

https://st-lab.tistory.com/167?category=856997