单链表: * 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 = 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 == 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中单链表的介绍以及用法的详细内容,更多请关注其它相关文章!
辽远或偏僻的地方,而会常常想起这一次的旅行,想起那座山,那个城,那些人……