首页 > 代码库 > java-------单链表

java-------单链表

单链表:
* 1.链表可以是一种有序或无序的列表
* 2.链表的内容通常存储在内存中分散的为止
* 3.链表由节点组成,每一个节点具有相同的结构
* 4.节点分为数据域和链域,数据域存放节点内容,链域存放下一个节点的指针

 

package myLinkList;

public class MyLinkedList<T> {

/**
*Node:节点对象
* 包括数据域data和链域next(指向下一个节点对象)
*/
class Node {
  private T data;
  private Node next;
  public Node(){

  }
  //节点初始化
  public Node(T data,Node next){
    this.data = http://www.mamicode.com/data;
    this.next = next;
  }
}

private Node header;//链表头节点
private Node tailer;//链表尾节点
private int size;//链表长度(节点个数)


/**
* 链表初始化
*/
public MyLinkedList() {//空参构造
  header = null;
  tailer = null;
}
public MyLinkedList(T data) {//有参构造
  header = new Node(data,null);//创建头结点
  tailer = header;
  size++;
}

/**
* 求链表长度
* @return
*/
public int getSize() {
  return size;
}

/**
* 返回索引为index的节点的数据
* @param index 索引
* @return
*/
public T get(int index) {
  if(index < 0 || index > size-1)
    throw new IndexOutOfBoundsException("索引越界");
  return getIndexNode(index).data;
}

public Node getIndexNode(int index){
  if(index < 0 || index > size-1)
    throw new IndexOutOfBoundsException("索引越界");
  Node current = header;
  for(int i = 0;i < size; i++) {
    if(i == index) {
    return current;
  }
  current = current.next;
}
  return null;
}

/**
* 返回element在在链表位置,如果不存在,则返回-1
* @param tdata
* @return
*/
public int getIndex(T element) {
  if(element == null)
    return -1;
  Node current = header;
  for(int i = 0; i < size; i++) {
    if(current.data =http://www.mamicode.com/= element){
    return i;
  }
  current = current.next;
}
  return -1;
}



/**
* 在链表末端添加element
* @param element
*/
public void add(T element) {
  Node n = new Node(element,null);
  if(header == null){
  header = n;
  tailer = header;
}else{
  tailer.next = n;
  tailer = n;
}
  size++;
}

/**
* 在链表头部添加element
* @param element
*/
public void addAtheader(T element) {
  header = new Node(element,header);
  if(tailer == null){
    tailer = header;
  }
  size++;
}

/**
* 在index位置后边插入元素
* @param index
* @param element
*/
public void insert(int index,T element) {
  if(index<0 || index>size-1) {
    throw new IndexOutOfBoundsException("索引越界");
  }
  if(header==null){
    add(element);
  }else{
    if(index==0){
    addAtheader(element);
  }else{
      Node current = getIndexNode(index);
      Node insertNode = new Node(element,current.next);
      current.next = insertNode;
      size++;
    }
  }
}
/**
* 删除任意位置的节点
* @param index
* @return
*/
public T deleteNode(int index){
  if(index<0 || index>size-1)
    throw new IndexOutOfBoundsException("索引越界");
  if(index == 0){//在头部删除元素
    Node n = header;//记录头节点
    header = header.next;//将头指针指向下一个节点
    size--;
    return n.data;//输出记录节点的内容
  }else{//在其他位置删除
    Node current = getIndexNode(index);//获取当前节点
    Node pre = getIndexNode(index-1);//获取前一个节点
    pre.next = current.next;//将前一个节点的链域设为null
    size--;
    return current.data;//返回删除节点的数据域
  }


}
/**
* 删除头节点
* @return
*/
public T deleteHeader(){
  return deleteNode(0);
}
/**
* 删除尾节点
* @return
*/
public T deleteTailer(){
return deleteNode(size-1);
}

//清空节点
public void clear(){
  header = null;
  tailer = null;
  size = 0;
}

/**
* toString();
*/
public String toString(){
  if(size == 0)
    return "[]";
  Node current = header;
  StringBuilder sb = new StringBuilder();
  sb.append("[");
  while(current.next != null) {
    sb.append(current.data).append(" ");
    current = current.next;
  }
  sb.append(current.data).append("]");
  return sb.toString();
}


public static void main(String[] args) {
  MyLinkedList<String> link = new MyLinkedList<>();
  link.add("header");
  link.add("11");
  link.add("22");
  link.add("33");
  link.addAtheader("newheader");
  link.insert(2, "1.5");;

  System.out.println(link.getIndex("11"));
  System.out.println(link.getIndex("88"));
  System.out.println(link.get(0));
  System.out.println(link.getSize());
  System.out.println(link.deleteHeader());
  System.out.println(link.deleteTailer());
  System.out.println(link.deleteNode(1));
  System.out.println(link);
  link.clear();
  System.out.println(link);

  }

}

java-------单链表