一、基本操作
二、编码思路
1，按照普适思路编写；2，注意判空保证程序健壮性（实际上判空也是考虑全面）
三、实现了上述基本操作的单链表
增
1，按照普适思路编写；2，注意判空
/**
* 插入到单链表尾部
* 【增】
* @param data
* @return
*/
public boolean addNode(E data){
Node newNode=new Node(data);
// 找到最后一个节点
Node p=head;
while(p!=null && p.next!=null){
p=p.next;
}// 找到尾节点
if(p==null){
// 说明原来链表为空
head=newNode;
}else{
// p.next==null;
// 原来链表不为空
p.next=newNode;
}
return true;
}
/*public boolean addNode2(E data){
Node newNode=new Node(data);
if(head==null){
head=newNode;
}else{
// 找到最后一个节点
Node p=head;
while(p.next!=null){
p=p.next;
}
p.next=newNode;
}
return true;
}*/
/**
* 将数据插入后使得其索引为index
* 链表的插入需要知道前一节点
* @param index：[0,size]区间内
* @param data
* @return
*/
public boolean add(int index,E data){
if(index <0 || index>length()){
throw new ArrayIndexOutOfBoundsException();
}
Node newNode=new Node(data);
if(index==0){
newNode.next=head;
head=newNode;
}else{
// 找到第index-个节点
Node p=node(index-1);
newNode.next=p.next;
p.next=newNode;
}
return true;
}
删
1，按照普适思路编写；2，注意判空
/**
* 删除元素值为data的元素
* @param data
* @return
*/
public boolean removeElement(E e){
if(e==null){
Node pre=null;
Node p=head;
// 遍历整个链表
while(p!=null){
if(p.data==null){
// 找到这个元素了
if(pre!=null){
pre.next=p.next;
}else{
head=p.next;
}
return true;
}else{
// 未找到
pre=p;
p=p.next;
}
}
}else{
Node pre=null;
Node p=head;
// 遍历整个链表
while(p!=null){
if(e.equals(p.data)){
// 删除
if(pre!=null){
pre.next=p.next;
}else{
head=head.next;
}
return true;
}else{
// 未找到
pre=p;
p=p.next;
}
}
}
return false;
}
/**
* 删除索引为index的元素
* @param index
* @return
*/
public boolean removeForIndex(int index){
checkElementIndex(index);
if(index==0){
head=head.next;
}else{
// 找出第index个元素，及其pre元素
Node pre=head;
Node p=head.next;
for(int i=1;i<index;i++){
pre=p;
p=p.next;
}
// 跳出循环时：p指向第index个元素
pre.next=p.next;
}
return true;
}
改
注意其中找出第index节点的方法
/**
* 修改索引值为index的元素值
* @param index
* @param e
* @return
*/
public boolean set(int index,E e){
checkElementIndex(index);
// 找出第index个元素
Node p=head;
for(int i=0;i<index;i++){
p=p.next;
}
p.data=e;
return true;
}
查
/**
* 得到索引值为index处的元素值
* @param index
* @return
*/
public E get(int index){
checkElementIndex(index);
// 找到第index个元素
Node p=head;
for(int i=0;i<index;i++){
p=p.next;
}
return p.data;
}
源码
/**
*
* <p>Description: 单链表</p>
* @author 杨丽金
* @date 2018-9-9
* @version 1.0
*/
public class MySingleList<E> {
class Node{
E data;
Node next;
Node(E data){
this.data=data;
}
}
// 链表头
private Node head=null;
/**
* 插入到单链表尾部
* 【增】
* @param data
* @return
*/
public boolean addNode(E data){
Node newNode=new Node(data);
// 找到最后一个节点
Node p=head;
while(p!=null && p.next!=null){
p=p.next;
}// 找到尾节点
if(p==null){
// 说明原来链表为空
head=newNode;
}else{
// p.next==null;
// 原来链表不为空
p.next=newNode;
}
return true;
}
/*public boolean addNode2(E data){
Node newNode=new Node(data);
if(head==null){
head=newNode;
}else{
// 找到最后一个节点
Node p=head;
while(p.next!=null){
p=p.next;
}
p.next=newNode;
}
return true;
}*/
/**
* 将数据插入后使得其索引为index
* 链表的插入需要知道前一节点
* @param index：[0,size]区间内
* @param data
* @return
*/
public boolean add(int index,E data){
if(index <0 || index>length()){
throw new ArrayIndexOutOfBoundsException();
}
Node newNode=new Node(data);
if(index==0){
newNode.next=head;
head=newNode;
}else{
// 找到第index-个节点
Node p=node(index-1);
newNode.next=p.next;
p.next=newNode;
}
return true;
}
/**
* 得到第index个节点
* @param index：[0,size-1]，index从0开始
* @return
*/
private Node node(int index) {
Node p=head;
for(int i=0;i<index;i++){
p=p.next;
}
return p;
}
/**
* 删除元素值为data的元素
* @param data
* @return
*/
public boolean removeElement(E e){
if(e==null){
Node pre=null;
Node p=head;
// 遍历整个链表
while(p!=null){
if(p.data==null){
// 找到这个元素了
if(pre!=null){
pre.next=p.next;
}else{
head=p.next;
}
return true;
}else{
// 未找到
pre=p;
p=p.next;
}
}
}else{
Node pre=null;
Node p=head;
// 遍历整个链表
while(p!=null){
if(e.equals(p.data)){
// 删除
if(pre!=null){
pre.next=p.next;
}else{
head=head.next;
}
return true;
}else{
// 未找到
pre=p;
p=p.next;
}
}
}
return false;
}
/**
* 删除索引为index的元素
* @param index
* @return
*/
public boolean removeForIndex(int index){
checkElementIndex(index);
if(index==0){
head=head.next;
}else{
// 找出第index个元素，及其pre元素
Node pre=head;
Node p=head.next;
for(int i=1;i<index;i++){
pre=p;
p=p.next;
}
// 跳出循环时：p指向第index个元素
pre.next=p.next;
}
return true;
}
// 必须为[0,size-1]范围内
private void checkElementIndex(int index){
if(index <0 || index >= length()){
throw new IndexOutOfBoundsException();
}
}
/**
* 返回链表长度
* @return
*/
public int length(){
if(head==null){
return 0;
}
Node p=head;
int len=1;
while(p.next!=null){
p=p.next;
len++;
}
return len;
}
public void print(){
if(head==null){
return ;
}
Node p=head;
while(p!=null){
System.out.print(p.data+",");
p=p.next;
}
System.out.println();
}
/**
* 修改索引值为index的元素值
* @param index
* @param e
* @return
*/
public boolean set(int index,E e){
checkElementIndex(index);
// 找出第index个元素
Node p=head;
for(int i=0;i<index;i++){
p=p.next;
}
p.data=e;
return true;
}
/**
* 得到索引值为index处的元素值
* @param index
* @return
*/
public E get(int index){
checkElementIndex(index);
// 找到第index个元素
Node p=head;
for(int i=0;i<index;i++){
p=p.next;
}
return p.data;
}
public static void main(String[] args) {
MySingleList<Integer> list=new MySingleList<Integer>();
System.out.println("链表长度："+list.length());
list.addNode(2);
list.addNode(3);
list.addNode(5);
list.addNode(-1);
list.print();
System.out.println("链表长度："+list.length());
list.add(0, 0);
list.add(1,1);
list.add(6,99);
list.print();
System.out.println("链表长度："+list.length());
list.removeElement(0);
list.print();
System.out.println("链表长度："+list.length());
list.removeElement(3);
list.print();
System.out.println("链表长度："+list.length());
list.removeElement(99);
list.print();
System.out.println("链表长度："+list.length());
list.removeForIndex(0);
list.print();
System.out.println("链表长度："+list.length());
list.removeForIndex(1);
list.print();
System.out.println("链表长度："+list.length());
list.removeForIndex(1);
list.print();
System.out.println("链表长度："+list.length());
list.set(0, 100);
list.print();
System.out.println("链表长度："+list.length());
System.out.println("第0个元素："+list.get(0));
}
}
网友评论