• 单向链表增删改查的操作
  • 反转单向链表
  • 判断单向链表是否有环

写一个大家都比较熟悉的数据结构:单向链表。 虽然java的API里面已经提供了单向链表的类,大家可以直接拿来用,但是通过自己的编写也更能够让我们了解其中实现的过程,而且我们还可以写一些比较个性化的方法作为属于自己的数据结构。这里主要是介绍一些常用结构里面都会用到的方法,以及链表具体是如何操作的。

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序从头部开始读取,链表是使用指针进行构造的列表,又称为结点列表。因为链表是由一个个结点组装起来的,其中每个结点都有指针成员变量指列表中的下一个结点,由head指针指向第一个成为表头的结点而终止于最后一个指向nuLL的指针。

首先定义一个简单的Person类

里面仅仅包含两个元素姓名和年龄


public class Person {

    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]";
    }
	
}

接下来构造PersonNode节点

PersonNode节点拥有一个Person对象和PersonNode节点的指针


public class PersonNode {

    private Person person;
    private PersonNode nextNode;
	
    public PersonNode(Person person, PersonNode nextNode) {
        this.person = person;
        this.nextNode = nextNode;
    }

    public Person getPerson() {
        return person;
    }

    public void setPerson(Person person) {
        this.person = person;
    }

    public PersonNode getNextNode() {
        return nextNode;
    }

    public void setNextNode(PersonNode nextNode) {
        this.nextNode = nextNode;
    }

}

增加节点

新添加的节点指向头结点


public void addNode(Person p) {
    if (isEmpty()) {
        head = new PersonNode(p, null);
    } else {
        head = new PersonNode(p, head);
    }
    size++;
}

删除节点


public void deleteNode(String personName) {
    //情况一:链表节点数为0
    if (isEmpty()) {
        return ;
    }
    //情况二:链表中无此节点
    if (!contains(personName)) {
        return ;
    }
    //情况三:链表中只有一个节点且匹配
    if (size == 1) {
        head = null;
        size = 0;
        return ;
    }
    //情况四:删除的是第一个链表节点
    int index = 0;//被删除节点的索引
    for (PersonNode pn = head; pn != null; pn = pn.getNextNode()) {
        if (pn.getPerson().getName().equals(personName)) {
            break;
        } else {
            index++;
        }
    }
    if (index == 0) {
        head = new PersonNode(head.getNextNode().getPerson(), head.getNextNode().getNextNode());
        size--;
        return ;
    }
    //情况五:删除的不是第一个链表节点
    int preIndex = 0;//被删除节点的前一个节点的索引
    for (PersonNode pn = head; pn != null; pn = pn.getNextNode()) {
        if (preIndex == index - 1) {
            if (index == size - 1) {//删除的节点是最后一个节点
                pn.setNextNode(null);
            } else {
                pn.setNextNode(pn.getNextNode().getNextNode());
            }
            size--;
            return ;
        }
        preIndex++;
    }
}

修改人名


public void modifyPersonName(String oldName, String newName) {
	if (newName == null || oldName == null) {
		return ;
	}
	Person p = searchPerson(oldName);
	if (p == null) {
		return ;
	}
	p.setName(newName);
}

修改年龄


public void modifyPersonAge(String personName, int age) {
	if (personName == null) {
		return ;
	}
	if (age <= 0) {
		return ;
	}
	Person p = searchPerson(personName);
	if (p == null) {
		return ;
	}
	p.setAge(age);
}

根据人名搜索这个人的信息


public Person searchPerson(String personName) {
	for (PersonNode pn = head; pn != null; pn = pn.getNextNode()) {
		if (pn.getPerson().getName().equals(personName)) {
			return pn.getPerson();
		}
	}
	return null;
}

根据人名搜索这个人的节点


public PersonNode searchNode(String personName) {
	for (PersonNode pn = head; pn != null; pn = pn.getNextNode()) {
		if (pn.getPerson().getName().equals(personName)) {
			return pn;
		}
	}
	return null;
}

链表中是否包含该名字的节点


public boolean contains(String personName) {
	if (!isEmpty()) {
		for (PersonNode pn = head; pn != null; pn = pn.getNextNode()) {
			if (pn.getPerson().getName().equals(personName)) {
				return true;
			}
		}
	}
	return false;
}

是否为空


public boolean isEmpty() {
	return size == 0;
}

打印所有节点


public void printAllNode() {
	if (!isEmpty()) {
		for (PersonNode pn=head; pn != null; pn = pn.getNextNode()) {
			System.out.println(pn.getPerson().toString());
		}
	}
}

链表反转


public PersonNode reverse() {
	if (isEmpty()) {
		return null;
	}
	PersonNode pre = head;
	PersonNode cur = head.getNextNode();
	PersonNode next;
	while (cur != null) {
		next = cur.getNextNode();
		cur.setNextNode(pre);
		pre = cur;
		cur = next;
	}
	head.setNextNode(null);
	head = pre;
	return head;
}

判断链表是否为环链表

两个指针slow,fast都从头开始遍历单链表,slow每次向前走1步,fast每次向前走2步,如果fast碰到了null,说明环不存在;如果fast碰到本应在身后的slow说明环存在。


public boolean isLoop() {
	if (head == null || head.getNextNode() == null) {
		return false;
	}
	PersonNode slow = head;
	PersonNode fast = head;
	while (fast != null && fast.getNextNode() != null) {
		slow = slow.getNextNode();
		fast = fast.getNextNode().getNextNode();
		if (slow == fast) {
			return true;
		}
	}
	return false;
}

详细内容请参考GitHub源码