线性表的链式存储结构之单链表类的实现_Java
在之前的两篇博文——线性表接口的实现_Java和线性表的链式存储结构之单链表结点类的实现_Java中,我们实现了线性表的接口和单链表的结点类,今天让我们来实现线性表的链式存储结构——单链表类。
注释写得很详细了,直接看吧:
package dataStructure.linearList; import dataStructure.linearList.Node; //导入单链表结点类 public class SinglyLinkedList<E> implements LList<E> //单链表类,实现线性表接口 { protected Node<E> head; //头指针,指向单链表第一个结点 public SinglyLinkedList() //构造空单链表 { this.head = null; } public SinglyLinkedList(Node<E> head) //构造指定头指针的单链表 { this.head = head; } public boolean isEmpty() //判断单链表是否为空 { return this.head == null; } public int length() //返回单链表长度,单链表遍历算法 { int i = 0; Node<E> p = this.head; while(p != null) { i ++; p = p.Next; } return i; } public E get(int index) //返回序号为index的对象,若单链表为空或序号错误则返回null { if(this.head != null && index >= 0) { int j = 0; Node<E> p = this.head; while(p != null && j < index) { j ++; p = p.Next; } if(p !=null) { return (E)p.Data; } } return null; } public E set(int index,E element) //设置序号为index的对象为element,若操作成功,返回原对象,否则返回null { if(this.head != null && index >= 0 && element != null) { int j = 0; Node<E> p = this.head; while(p != null && j < index) { j ++; p = p.Next; } if(p != null) { E old = (E)p.Data; p.Data = element; return old; //若操作成功,则返回原对象 } } return null; //操作不成功 } public boolean add(int index,E element) //插入element对象,插入后对象序号为index,若操作成功返回true { if(element ==null) { return false; //不能添加空对象(null) } if(this.head == null || index <= 0) //头插入 { Node<E> q = new Node<E>(element); q.Next = this.head; this.head = q; //this.head = new Node(element,this.head); //头插入,相当于上述3句 } else //单链表不空且index>=1 { int j = 0; Node<E> p = this.head; while(p.Next != null && j < index - 1) //寻找插入位置 { j ++; p = p.Next; } Node<E> q = new Node<E>(element); //中间/尾插入 q.Next = p.Next; //q插入在p结点之后 p.Next = q; //p.Next = new Node(element,p.Next); //中间/尾插入,相当于上述3句 } return true; } public boolean add(E element) //在单链表最后插入对象 { return add(Integer.MAX_VALUE,element); } public E remove(int index) //移去序号为index的对象,若操作成功则返回被移去的对象,否则返回null { E old = null; if(this.head != null && index >= 0) { if(index == 0) //头删除 { old = (E)this.head.Data; this.head = this.head.Next; } else //中间/尾删除 { int j = 0; Node<E> p = this.head; while(p.Next != null && j < index - 1) //定位到待删除结点的前驱结点 { j ++; p = p.Next; } if(p.Next != null) { old = (E)p.Next.Data; //若操作成功,返回被移去对象 p.Next = (p.Next).Next; //删除p的后继结点 } } } return old; } public void clear() //清空单链表 { this.head = null; } public String toString() //返回所有元素值对应的字符串 { String str = "("; Node<E> p = this.head; while(p != null) { str += p.Data.toString(); p = p.Next; if(p != null) { str += ","; } } return str + ")"; } }
在下一篇博文中我将和大家讨论有关单链表的toString()的递归算法以及单链表的逆转问题。敬请期待。
您阅读此文共耗时分秒