链表在我们java中也是一种基础的数据结构,可以理解成是一种和数组同级的数组结构,正如我们所知,在我们使用这集合ArrayList和LinkedList的时候,总会学习底层数组实现的ArrayList和双向链表实现的LinkedList的区别。在这里,我们将要讲说的是单向链表的简单实现,让我们体会一下链表在实现增删改查的时候是怎么样的一个操作,在和前边涉及到的数组的增删改查进行对比,得到我们学习的结论,数组的增删效率低于链表结构,查改效率高于链表结构!
什么叫做单向链表,我们可以理解为一个一个节点链接起来的一条链子,从第一个开始有指向下一个的箭头,也就是说单向链表的每一个节点我们可以理解为是一个对象,里面包含了date内容属性,同时也包含了next下一个对象的属性。代码如下:
public class MyList { //定义一个头节点 private Node head; //定义一个节点内部类 class Node{ int date; Node next; public Node(int date){ this.date = date; } } /** * 获取链表的长度 * @return */ public int getSize(){ //判断是否头结点为空 if(head == null){ return 0; }else { Node current = head; int size = 1; while((current = current.next)!=null){ size++; } return size; } } /** * 判断链表是否为空 * @return */ public boolean isEmpty(){ if(head==null){ return true; }else { return false; } } /** * 根据节点信息判断是否包含这个节点 * @param date * @return */ public boolean contains(int date){ //判断头结点是否为空 if(head==null){ return false; }else { for(int i = 0;i < getSize();i++){ if(head.date==date){ return true; } head = head.next; } return false; } } /** * 根据下角标获取对象的节点 * @param index * @return */ public Node getNode(int index){ //对index的有效进行判断 if(index < 0 || index >= getSize()){ throw new IndexOutOfBoundsException(); }else { int i = 0; Node current = head; while(i < index){ current = current.next; i++; } return current; } } /** * 根据节点内容获取节点对象 * @param date * @return */ public Node getNodeByDate(int date){ //判断链表是否为空 if(getSize()==0){ return null; }else { for (int i = 0; i < getSize(); i++) { if(getNode(i).date == date){ return getNode(i); } } return null; } } /** * 插入头结点 * @param date */ public void addFirstNode(int date){ Node node = new Node(date); node.next = head; head = node; } /** * 在链表尾端插入节点 * @param date */ public void addLastNode(int date){ //判断头结点是否为空 if(head == null){ addFirstNode(date); }else { //获取原尾端节点 Node node = getNode(getSize()-1); //获取当前节点 Node nowNode = new Node(date); //建立连接 node.next = nowNode; } } /** * 在任意位置插入节点 * @param index * @param date */ public void addNode(int index,int date){ //判断index的有效性 if(index < 0 || index > getSize()){ throw new IndexOutOfBoundsException(); }else { if(index == 0){ addFirstNode(date); }else if(index == getSize()){ addLastNode(date); }else { //获取新的当前节点 Node nowNode = new Node(date); //获取上一个节点 Node node1 = getNode(index - 1); //获取旧的当前节点 Node node2 = getNode(index); //断开原来节点的连接 node1.next = nowNode; //建立与node2的连接 nowNode.next = node2; } } } /** * 删除任意位置的节点 * @param index */ public void deleteNode(int index){ //判断index的有效性质 if(index < 0 || index >= getSize()){ throw new IndexOutOfBoundsException(); }else { //判断是否是头结点 if(index == 0){ head.next = null; head = head.next; }else { //获取删除节点的上一个节点 Node node1 = getNode(index - 1); //获取当前删除节点 Node nowNode = getNode(index); //建立上一个节点和下一个节点的连接 node1.next = nowNode.next; //断开删除节点和下一个节点的连接 nowNode = nowNode.next; } } } /** * 打印所有的节点信息 */ public void printAll(){ Node current = head; while(current!=null){ System.out.println(current.date); current = current.next; } } /** * 打印index以后的所有节点信息 * @param index */ public void printFromIndex(int index){ //判断index的有效 if(index < 0 || index >= getSize()){ throw new IndexOutOfBoundsException(); }else { //获取当前节点 Node node = getNode(index); while(node!=null){ System.out.println(node.date); node = node.next; } } } /** * 进行测试所有的方法 * @param args */ public static void main(String[] args) { MyList list = new MyList(); list.addFirstNode(1); list.addLastNode(2); list.addFirstNode(3); list.addLastNode(4); list.addNode(3, 5); list.deleteNode(3); list.printAll(); System.out.println(list.isEmpty()); System.out.println(list.getSize()); System.out.println(list.getNodeByDate(1)); System.out.println(list.getNode(2)); list.printFromIndex(2); } }
在上述代码中就是单向链表的简单实现,总的来说我们需要注意的是在输入数据时候,比如下标,我们需要对下标的合法性就行判断在进行操作,我们应该考虑到多种异常情况,然后也就比较简单了。明天我们将继续讲述关于单向链表的一些简单操作问题,如以下
1、求单链表中节点的个数
2、查找单链表中的倒数第k个结点
3、查找单链表中的中间结点
4、合并两个有序的单链表,合并之后的链表依然有序
5、单链表的反转
6、从尾到头打印单链表
7、判断单链表是否有环
8、取出有环链表中,环的长度
9、单链表中,取出环的起始点
10、判断两个单链表相交的第一个交点