java实现单链表的链式存储

仅用于学习记录 链表作为重要的数据结构，HashMap的底层结构都是链表结构，链表以结点作为存储单元，结点由存储的数值+指向后序结点的指针。

单链表结点

package shiyan1; public class Node<T>{ T data;//数据域，存储数据 Node<T> next;//地址域，引用后继节点 public Node(){//空参构造，会用默认的值去初始化成员 this(null, null); } public Node(T data,Node<T> next){ this.data = data; this.next = next; } public String toString(){ return this.data.toString(); } public static void main(String[] args) { // TODO Auto-generated method stub } }

Node的用途 T作为泛型，定义Node中存储的数值的类型

链表的实现

package shiyan1; import shiyan1.List; import shiyan1.Node; interface List<T>{ void insert(int index,T data); T remove(int i); boolean isEmpty(); String toString(); void reserveLink(); } public class SinglyList <T> implements List<T>{ Node<T> head = null;//单链表的头指针head是一个结点引用，令其为null表示空链表 public boolean isEmpty() {//判断链表是否为空 return this.head.next==null; } public T get(int i){ Node<T> p = this.head.next; for(int j=0;p!=null && j<i;j++) p=p.next; return p.data; } //某一位置结点的增添 public void insert(int index, T data) { // TODO Auto-generated method stub if(head==null){ head = new Node<T>(data,null); return; } Node<T> front = this.head; for(int j=0;front.next!=null && j<index; j++) front = front.next; front.next = new Node<T>(data,front.next); //return front.next; } //链表某一位置结点的删除 public T remove(int i) { // TODO Auto-generated method stub Node<T> front = this.head; for(int j=0;front.next!=null&&j<i-1;j++){ front=front.next; } if(i==0 && head!=null) { head = head.next; } if(i>0 && front.next!=null){ T x = front.next.data; front.next = front.next.next; return x; } return null; } //链表的输出 public void printLink(){//head指向head引用结点 // Node<T> curNode = head; while(curNode !=null){ System.out.print(curNode.data+" "); curNode = curNode.next; } System.out.println(); } //链表的反转 public void reserveLink(){ Node<T> curNode = head;//头结点 Node<T> preNode = null;//前一个结点 while(curNode != null){ Node<T> nextNode = curNode.next;//保留下一个结点 curNode.next = preNode;//指针反转 preNode = curNode;//前结点后移 curNode = nextNode;//当前结点后移 } head = preNode; } }

测试类

package shiyan1; public class text { public static void main(String[] args) { // TODO Auto-generated method stub SinglyList<String> list = new SinglyList<String>(); list.insert(0, "A"); list.insert(1, "B"); list.printLink(); //list.remove(0); //list.printLink(); list.reserveLink(); list.printLink(); } }