[오라클자바community]Java Singly Linked List 예제

<<<<<<< 단순연결 리스트 >>>>>>>>>
배열의 경우 불필요한 메모리 낭비, 새로운 자료의 삽입및 삭제시
번거러우며, 시간이 많이 걸린다는 단점이 있습니다.
이 경우 연결리스트(Linked List)를 이용하면 메모리를 효율적으로
사용이 가능하며 자료의 삽이브 삭제가 용이하게 이루어지며,
처리시간을 단축시킬수 있습니다.

오라클자바커뮤니티에서 설립한 오엔제이프로그래밍 실무교육센터

(신입사원채용무료교육, 오라클SQL, 튜닝, 힌트,자바프레임워크, 안드로이드, 아이폰, 닷넷)  

www.onjprogramming.co.kr

일반적으로 리스트의 한 항목은 노드(Node)라고 하며 각각으ㅢ
노드는 데이터 부분과 다음 노드를 가리키는 포인터 값을 저장하는
링크부분으로 구성됩니다.


단순연결리스트의 경우엔 노드가 한쪽 방향으로 연결되어
있으며 맨 마지막 노드의 다음 노드를 가리키는 포인터값은
Null입니다.

아래에 2가지의 예제가 있으니, 참조바랍니다.

class ChainNode  {          
  Object element;
  ChainNode next;
   
  ChainNode() {}
 
  ChainNode(Object element)
  {this.element = element;}

  ChainNode(Object element, ChainNode next)
  {this.element = element;  this.next = next;}
}




public class MyLinkedList {
    protected ChainNode firstNode;
protected int size;

    public MyLinkedList() {
firstNode = null;
size = 0;
    }
   
    public void add(int index, Object theElement)
      {
            if (index < 0 || index > size)    // invalid list position
                  throw new IndexOutOfBoundsException
                            ("index = " + index + "  size = " + size);
            if (index == 0)      // insert at front
                firstNode = new ChainNode(theElement, firstNode);
            else
            { // find predecessor of new element
                  ChainNode p = firstNode;
                  for (int i = 0; i < index - 1; i++)
                        p = p.next;              // insert after p
                  p.next = new ChainNode(theElement, p.next);
            }
            size++;
  }


   
  public Object remove(int index) {
    checkIndex(index);
   
    Object removedElement;
    if (index == 0)      // remove first node
    {
          removedElement = firstNode.element;
          firstNode =firstNode.next;
    } else  {  // use q to get to predecessor of desired node
          ChainNode q = firstNode;
          for (int i = 0; i < index - 1; i++)
                q = q.next;  removedElement = q.next.element;
          q.next = q.next.next;    // remove desired node
        }
      size--;
      return removedElement;
  }

  public Object get(int index) {
      checkIndex(index);
   
      // move to desired node
      ChainNode currentNode = firstNode;
      for (int i = 0; i < index; i++)
            currentNode = currentNode.next;
 
      return currentNode.element;
    }



    /* return true if list is empty */
      public boolean isEmpty()
      {return size == 0;}
   
      /* return current number of elements in list */
      public int size()
      {return size;}


  void checkIndex(int index)  {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException
              ("index = " + index + "  size = " + size);
      }

}
class Main {
    public static void main(String[] args) {
MyLinkedList names = new MyLinkedList();
String name = "";

names.add(0, new String("Scott"));
names.add(0, new String("Tiger"));
names.add(2, new String("Swan"));

// Print out the list
System.out.println("\n list의 내용:");
for(int i = 0; i < names.size(); i++) {
name = (String)names.get(i);
System.out.println("  Element " + i + ": " + name);
}

// Delete item
names.remove(0);

System.out.println("\n list의 내용:");
for(int i = 0; i < names.size(); i++) {
name = (String)names.get(i);
System.out.println("  Element " + i + ": " + name);
}  
}
}



===============================================================================


//element, next를 private 으로 선언
//외부에서의 접근은 메소드를 통해서...
class ChainNode  {            
private Object element;          //Node안에 저장된 item(Object)
private ChainNode next;        //다음  Node를 가리키는 Reference

ChainNode() {}  
    ChainNode(Object newElement) {
element = newElement;
next = null;
    }

    ChainNode(Object newElement, ChainNode nextNode) {
element = newElement;
next = nextNode;
    }
 
    public void setElement(Object newItem) {
element = newItem;
    }

    public Object getElement() {
return element;
    }

    public void setNext(ChainNode nextNode) {
next = nextNode;
    }

    public ChainNode getNext() {
return next;
    }
}




//이전 노드를 찾는 별도의 메소드 존재
public class MyLinkedList {
    // The Node of the list
    private ChainNode firstNode;

    // The number of elements in the list
    private int size;  

    public MyLinkedList() {
firstNode = null;
size = 0;
    }
   
    public void add(int index, Object element)  {
// Check for a valid index
if (index < 0 || index > size) throw new IndexOutOfBoundsException
              ("index = " + index + "  size = " + size);

// Case 1: index == 0
// Insert at the head of the list
if(index == 0) {
ChainNode newNode = new ChainNode(element);
newNode.setNext(firstNode);
firstNode = newNode;
size++;
return;
}

// Case 2: index != 0
// Insert somewhere else in the list
ChainNode previousNode = find(index);
ChainNode newNode = new ChainNode(element);
newNode.setNext(previousNode.getNext());
previousNode.setNext(newNode);
size++;
    }
   
    public void remove(int index)  {
// Check for a valid index
checkIndex(index);

// Case 1: index == 0
// Delete the firstNode of the list
if(index == 0) {
firstNode = firstNode.getNext();
size--;
return;
}

// Case 2: index != 0
// Delete something in the middle of the list
// 교재에서 처럼 직접 Node를 검색해도 된다.
ChainNode previousNode = find(index);
previousNode.setNext(previousNode.getNext().getNext());
size--;
    }

    public Object get(int index)  {
// Check for a valid index
checkIndex(index);

// Case 1: index == 0
// Get the firstNode of the list
if(index == 0) {
return firstNode.getElement();
}

// Case 2: index != 0
// Get something from the middle of the list
// 교재에서 처럼 루프를 돌면서 index번째의 Node를
// 직접 찾아도 되나 예제에서는 find() 메소드를 구현해 놓음
ChainNode previousNode = find(index);
return((previousNode.getNext()).getElement());
    }


    // Returns the node *before* the desired one.
    private ChainNode find(int index) {
int i;
ChainNode currentNode;

// Traverse the links until we get to the one just before the desired one.
currentNode = firstNode;
for(i = 0; i < size; i++) {
    if(i == index-1)
return(currentNode);

    // bad index
    if(currentNode == null)
return(null);

    currentNode = currentNode.getNext();
}
return null;
    }

  // empties the list
    public void removeAll() {
firstNode = null;
size = 0;
    }

    // returns the length of the list
    public int size() {
return size;
    }

void checkIndex(int index)
  {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException
              ("index = " + index + "  size = " + size);
    }

}



class Main {
    public static void main(String[] args) {
MyLinkedList names = new MyLinkedList();
String name = "";

names.add(0, new String("Scott"));
names.add(0, new String("Tiger"));
names.add(2, new String("Swan"));

// Print out the list
System.out.println("\n list의 내용:");
for(int i = 0; i < names.size(); i++) {
name = (String)names.get(i);
System.out.println("  Element " + i + ": " + name);
}

// Delete item
names.remove(0);

System.out.println("\n list의 내용:");
for(int i = 0; i < names.size(); i++) {
name = (String)names.get(i);
System.out.println("  Element " + i + ": " + name);
}  
}
}
[출처] 오라클자바커뮤니티 - http://www.oraclejavanew.kr/bbs/board.php?bo_table=LecJavaAlgorithm&wr_id=65