一、基本操作
二睡互、編碼思路
1根竿，按照普適思路編寫陵像；2，注意判空保證程序健壯性（實(shí)際上判空也是考慮全面）
三寇壳、實(shí)現(xiàn)了上述基本操作的單鏈表
增
1醒颖，按照普適思路編寫；2壳炎，注意判空
/**
* 插入到單鏈表尾部
* 【增】
* @param data
* @return
*/
public boolean addNode(E data){
Node newNode=new Node(data);
// 找到最后一個(gè)節(jié)點(diǎn)
Node p=head;
while(p!=null && p.next!=null){
p=p.next;
}// 找到尾節(jié)點(diǎn)
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{
// 找到最后一個(gè)節(jié)點(diǎn)
Node p=head;
while(p.next!=null){
p=p.next;
}
p.next=newNode;
}
return true;
}*/
/**
* 將數(shù)據(jù)插入后使得其索引為index
* 鏈表的插入需要知道前一節(jié)點(diǎn)
* @param index：[0,size]區(qū)間內(nèi)
* @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-個(gè)節(jié)點(diǎn)
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;
// 遍歷整個(gè)鏈表
while(p!=null){
if(p.data==null){
// 找到這個(gè)元素了
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;
// 遍歷整個(gè)鏈表
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個(gè)元素腰耙，及其pre元素
Node pre=head;
Node p=head.next;
for(int i=1;i<index;i++){
pre=p;
p=p.next;
}
// 跳出循環(huán)時(shí)：p指向第index個(gè)元素
pre.next=p.next;
}
return true;
}
改
注意其中找出第index節(jié)點(diǎn)的方法
/**
* 修改索引值為index的元素值
* @param index
* @param e
* @return
*/
public boolean set(int index,E e){
checkElementIndex(index);
// 找出第index個(gè)元素
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個(gè)元素
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);
// 找到最后一個(gè)節(jié)點(diǎn)
Node p=head;
while(p!=null && p.next!=null){
p=p.next;
}// 找到尾節(jié)點(diǎn)
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{
// 找到最后一個(gè)節(jié)點(diǎn)
Node p=head;
while(p.next!=null){
p=p.next;
}
p.next=newNode;
}
return true;
}*/
/**
* 將數(shù)據(jù)插入后使得其索引為index
* 鏈表的插入需要知道前一節(jié)點(diǎn)
* @param index：[0,size]區(qū)間內(nèi)
* @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-個(gè)節(jié)點(diǎn)
Node p=node(index-1);
newNode.next=p.next;
p.next=newNode;
}
return true;
}
/**
* 得到第index個(gè)節(jié)點(diǎn)
* @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;
// 遍歷整個(gè)鏈表
while(p!=null){
if(p.data==null){
// 找到這個(gè)元素了
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;
// 遍歷整個(gè)鏈表
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個(gè)元素铲球，及其pre元素
Node pre=head;
Node p=head.next;
for(int i=1;i<index;i++){
pre=p;
p=p.next;
}
// 跳出循環(huán)時(shí)：p指向第index個(gè)元素
pre.next=p.next;
}
return true;
}
// 必須為[0,size-1]范圍內(nèi)
private void checkElementIndex(int index){
if(index <0 || index >= length()){
throw new IndexOutOfBoundsException();
}
}
/**
* 返回鏈表長(zhǎng)度
* @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個(gè)元素
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個(gè)元素
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("鏈表長(zhǎng)度："+list.length());
list.addNode(2);
list.addNode(3);
list.addNode(5);
list.addNode(-1);
list.print();
System.out.println("鏈表長(zhǎng)度："+list.length());
list.add(0, 0);
list.add(1,1);
list.add(6,99);
list.print();
System.out.println("鏈表長(zhǎng)度："+list.length());
list.removeElement(0);
list.print();
System.out.println("鏈表長(zhǎng)度："+list.length());
list.removeElement(3);
list.print();
System.out.println("鏈表長(zhǎng)度："+list.length());
list.removeElement(99);
list.print();
System.out.println("鏈表長(zhǎng)度："+list.length());
list.removeForIndex(0);
list.print();
System.out.println("鏈表長(zhǎng)度："+list.length());
list.removeForIndex(1);
list.print();
System.out.println("鏈表長(zhǎng)度："+list.length());
list.removeForIndex(1);
list.print();
System.out.println("鏈表長(zhǎng)度："+list.length());
list.set(0, 100);
list.print();
System.out.println("鏈表長(zhǎng)度："+list.length());
System.out.println("第0個(gè)元素："+list.get(0));
}
}
