بررسی لیست پیوندی
بر خلاف list که عناصر آرایه وار مستقیم روی حافظه ذخیره میشن، در لیست پیوندی (LinkedList) عناصر در گره (node) ها ذخیره میشن.
در لیست پیوندی (LinkedList) هر عنصر داخل یک node ذخیره میشه و هر node به node بعدی اشاره میکنه و آخرین node در حالت استاندارد به null اشاره میکنه؛ به عبارتی هر node به node بعدی زنجیر (link) میشه.
زمانی که LinkedList خالی باشه تنها یک node داخلش وجود داره، مقدار عنصری که داخل node نگهداری میشه null و node بعدی که بهش اشاره میکنه null است.
زمانی که بخوایم عناصر رو از ابتدا یا انتها حذف یا اضافه کنیم، استفاده از LinkedList بهینه تر از استفاده از list است؛ اما اگه بخوایم به عناصر با index به صورت تصادفی دسترسی داشته باشیم استفاده از list بهینه تر از LinkedList است.
ساختار لیست پیوندی
هر عنصر داخل یک node نگهداری میشه و هر node به node بعد از خودش (در صورتی که اخرین node نباشه) و به node قبل از خودش (در صورتی که اولین node نباشه) اشاره میکنه (Doubly LinkedList).
در زیر به صورت تصویری شرح داده شده که چطور عناصر در LinkedList نگهداری میشن.
انواع لیست پیوندی
انواع مختلفی از پیاده‌سازی لیست پیوندی (LinkedList) داریم که در ادامه سه تا از پیاده‌سازی های معروف رو بیان میکنیم.
توجه
در این مطلب فقط به جزییات Doubly LinkedList می پردازیم، نحوه ی پیاده‌سازی سایر LinkedList ها تقریبا مشابه است.
لیست پیوندی یک طرفه (Singly LinkedList)
در این نوع لیست پیوندی (LinkedList) هر node به node بعد خودش اشاره (point) میکنه تا آخرین node که node بعدش null است.
جستجو در این نوع LinkedList یک طرفه است یعنی برای پیدا کردن یک عنصر، جستجو از اولین node شروع میشه تا به node مورد نظر برسیم.
لیست پیوندی دو طرفه (Doubly LinkedList)
در این نوع لیست پیوندی هر node به node بعد از خودش و node قبل از خودش اشاره (point) میکنه و اولین node به null به عنوان node قبل از خودش اشاره میکنه و اخرین node به null به عنوان node بعد از خودش اشاره میکنه.
جستجو در این نوع LinkedList دو طرفه است، یعنی جستجو برای پیدا کردن یک عنصر، هم از اولین node به آخرین node امکان پذیر است هم از اخرین node به اولین node
لیست پیوندی مُدور (Circular LinkedList)
در این نوع LinkedList اخرین node بجای اشاره به null به عنوان node بعد خودش به اولین node در LinkedList اشاره می کنه.
بررسی گره (node) در لیست پیوندی
با افزودن هر عنصر یک گره (node) برای عنصر ایجاد میشه و عنصر داخل node نگهداری میشه؛ node علاوه بر نگهداری عنصر، به node قبل یا بعد خودش اشاره میکنه و اینجوری یک زنجیره بین عناصر توسط node ها ایجاد میشه.
به زبو‍‍ن ساده هر عنصر به عنصر بعد یا قبل از خودش به وسیله ی node گره زده میشه و این گره ها لیست پیوندی (LinkedList) رو تشکیل میدن.
فرم کلی node:
record node{
Node next
Node prev
E element
}
افزودن عنصر به لیست پیوندی
با افزودن هر عنصر به LinkedList یک node برای نگهداری عنصر ایجاد میشه، در LinkedList میتونیم node ها رو به ابتدا، انتها یا وسط سایر node ها اضافه کنیم.
افزودن node به ابتدای LinkedList
اگه بخوایم node رو به ابتدای LinkedList اضافه کنیم، node ایجاد شده به اولین node موجود در LinkedList اشاره میکنه. پیچیدگی زمان (time complexity) در این حالت O(1) است.
function addFirst(e: E){
newNode := Node(e)
if size = 0
lastNode := newNode
firstNode := newNode
else
newNode.next := firstNode
firstNode.prev := newNode
firstNode := newNode
size++
}
افزودن node به انتهای لیست پیوندی
اگه بخوایم node رو به انتهای LinkedList اضافه کنیم، اخرین node در LinkedList به node جدید اشاره میکنه؛ پیچیدگی زمان در این حالت O(1) است.
function addLast(e: E){
newNode := Node(e)
if size = 0
lastNode := newNode
firstNode := newNode
else
lastNode.next := newNode
newNode.prev := lastNode
lastNode := newNode
size++
}
افزودن node به وسط لیست پیوندی
اگه بخوایم node رو وسط node ها اضافه کنیم، node قبلی به node جدید اشاره میکنه و node جدید به node بعد؛ پیچیدگی زمان در این حالت O(n) است.
function add(index: int, e: E){
if index < 0 or (index >= size and size != 0)
throw IndexOutOfBoundException
newNode := Node(e)
if index == 0
addFirst(e)
else
count := 0
currentNode := firstNode
while count != index
currentNode := currentNode.next
count++
newNode.prev = currentNode.prev
currentNode.prev.next = newNode
newNode.next = currentNode
currentNode.prev = newNode
size++
}
صدا زدن عنصر با index در لیست پیوندی
برای صدا زدن یک عنصر با index در LinkedList باید node مربوط به index مورد نظر رو پیدا کنیم؛ صدا زدن یک عنصر در LinkedList دارای پیچیدگی زمان O(n) است.
function get(index: int): E {
if index < 0 or index > size - 1
throw IndexOutOfBoundException
count := 0
node := firstNode
while count != index
node := node.next
return node.element
}
حذف عنصر از لیست پیوندی
برای حذف یک عنصر از LinkedList باید node که عنصر مورد نظر رو نگهداری میکنه از زنجیره خارج کنیم؛ میتونیم یک عنصر رو از ابتدا، انتها یا وسط یک LinkedList حذف کنیم.
حذف عنصر از ابتدای LinkedList
برای حذف اولین عنصر از LinkedList، باید اولین node در LinkedList رو از زنجیره خارج کنیم.
function removeFirst(): E {
Node removedNode := null
if size = 0
throw NoSuchElementException
if size = 1
removedNode := firstNode
firstNode := null
lastNode := null
else
removedNode := firstNode
firstNode.next := firstNode.next.next
firstNode := firstNode.next
return removedNode.element
}
حذف عنصر از انتهای لیست پیوندی
برای حذف کردن آخرین عنصر از LinkedList، آخرین node رو از زنجیره خارج کنیم.
توجه
حذف اخرین node در Singly LinkedList دارای پیچیدگی زمان O(n) و در Doubly LinkedList دارای پیچیدگی زمان O(1) است؛ اما همانطور که گفتیم در این مطلب به Doubly LinkedList می پردازیم.
function removeLast(): E{
if size = 0
throw NoSuchElementException
removedNode := lastNode
if size = 1
firstNode := null
lastNode := null
else
prevNode := lastNode.prev
prevNode.next = null
lastNode := prevNode
return removedNode.element
}
حذف کردن عنصر با استفاده از index در لیست پیوندی
با استفاده از index در LinkedList میتونیم یک عنصر رو در ابتدا، وسط یا انتهای LinkedList حذف کنیم، برای این کار کافیه node مربوط به index رو پیدا کرده و از زنجیره حذفش کنیم.
function remove(index: int): E {
Node removedNode := null
if size = 0
throw NoSuchElementException
if index < 0 or index > size - 1
throw IndexOutOfBoundException
if size = 1
removedNode := firstNode
firstNode := null
lastNode := null
else
count := 0
Node node := firstNode
while count != index
count++
node := node.next
prevNode := node.prev
prevNode.next := node.next
return node.element
}
پیاده‌سازی لیست پیوندی در زبان های برنامه نویسی
میخوایم لیست پیوندی (LinkedList) رو به صورت عملی با استفاده از زبان های برنامه نویسی (جاوا، کاتلین، جاوااسکریپت و پایتون) پیاده‌سازی کنیم.
در این پیاده‌سازی تابع remove(index: int) به عنوان تمرین رها شده تا خودتون انجامش بدید.
برای راحتی یک دسترسی سریع به پیاده‌سازی ها رو در زیر قرار داده ایم.
پیاده‌سازی لیست پیوندی (LinkedList) با جاوا
در زیر یک لیست پیوندی (LinkedList) رو به صورت جنریک با جاوا پیاده‌سازی کرده ایم.
public class MyLinkedList<E> {
private Node<E> firstNode;
private Node<E> lastNode;
private int size;
public boolean isEmpty(){
return size == 0;
}
public int getSize() {
return size;
}
public void addFirst(E element){
Node<E> newNode = new Node<>(element, null, null);
if (isEmpty()){
firstNode = newNode;
lastNode = newNode;
}else{
firstNode.prev = newNode;
newNode.next = firstNode;
firstNode = newNode;
}
size++;
}
public void addLast(E element){
Node<E> newNode = new Node<>(element, null, null);
if (isEmpty()){
firstNode = newNode;
lastNode = newNode;
}else {
lastNode.next = newNode;
newNode.prev = lastNode;
lastNode = newNode;
}
size++;
}
public E getFirst(){
if(isEmpty()) throw NoSuchElementException("The LinkedList is empty");
return firstNode.element;
}
public E getLast(){
if(isEmpty()) throw NoSuchElementException("The LinkedList is empty");
return lastNode.element;
}
public E get(int index){
if (index < 0 || index > size - 1)
throw new IndexOutOfBoundsException("The index should be between 0 and " + (size -1));
Node<E> node;
if (size == 1){
node = firstNode;
}else {
int count = 0;
Node<E> currentNode = firstNode;
while (count != index){
currentNode = currentNode.next;
count++;
}
node = currentNode;
}
return node.element;
}
public E removeFirst(){
if (isEmpty())
throw new NoSuchElementException("The list is empty");
Node<E> removedNode;
if (size == 1){
removedNode = firstNode;
firstNode = null;
lastNode = null;
}else {
removedNode = firstNode;
firstNode = firstNode.next;
firstNode.prev = null;
}
size--;
return removedNode.element;
}
public void add(int index, E element){
if (index < 0 || (index >= size && size != 0)) throw new IndexOutOfBoundsException();
Node<E> newNode = new Node<>(element);
if (index == 0){
addFirst(element);
}else {
int count = 0;
Node<E> currentNode = firstNode;
while (count != index){
currentNode = currentNode.next;
count++;
}
newNode.prev = currentNode.prev;
currentNode.prev.next = newNode;
newNode.next = currentNode;
currentNode.prev = newNode;
size++;
}
}
public E remove(int index){
//TODO Left as an exercise
return null;
}
public E removeLast(){
if (size == 0)
throw new NoSuchElementException("List is empty");
Node<E> removedNode = lastNode;
if (size == 1){
firstNode = null;
lastNode = null;
}else {
Node<E> prevNode = lastNode.prev;
prevNode.next = null;
lastNode = prevNode;
}
size--;
return removedNode.element;
}
private static final class Node<E> {
private final E element;
private Node<E> next;
private Node<E> prev;
Node(E element, Node<E> next, Node<E> prev) {
this.element = element;
this.next = next;
this.prev = prev;
}
}
}
پیاده‌سازی لیست پیوندی با کاتلین
در زیر یک لیست پیوندی (LinkedList) رو با کاتلین پیاده‌سازی کرده ایم.
class MyLinkedList<E> {
private var firstNode: Node<E>? = null
private var lastNode: Node<E>? = null
var size = 0
val empty get() = size == 0
fun addFirst(element: E){
val newNode: Node<E> = Node(element)
if (size == 0) {
firstNode = newNode
lastNode = newNode
}else{
newNode.next = firstNode
firstNode!!.prev = newNode
firstNode = newNode
}
size++
}
fun addLast(element: E){
if (size == 0){
firstNode = Node(element)
lastNode = Node(element)
}else{
val node = Node(element)
node.prev = lastNode
lastNode!!.next = node
lastNode = node
}
size++
}
fun getFirst(): E?{
return firstNode?.element
}
fun getLast(): E?{
return lastNode?.element
}
fun get(index: Int): E? {
if (index !in 0..<size)
throw IndexOutOfBoundsException("index should be between 0 to ${size - 1}")
if (empty)
throw NoSuchElementException("The List is empty")
var node: Node<E>?
var count = 0
var currentNode = firstNode
while (count != index ){
currentNode = currentNode?.next
count++
}
node = currentNode
return node?.element
}
fun removeFirst(): E {
if (empty)
throw NoSuchElementException("There's no element in list")
val node: Node<E>
if (size == 1) {
node = firstNode!!
firstNode = null
lastNode = null
} else{
node = firstNode!!
firstNode = firstNode!!.next
firstNode!!.prev = null
}
size--
return node.element
}
fun add(index: Int, element: E){
if (index < 0 || (index >= size && size != 0)) throw IndexOutOfBoundsException()
val newNode: Node<E> = Node(element)
if (index == 0) {
addFirst(element)
} else {
var count = 0
var currentNode: Node<E>? = firstNode
while (count != index) {
currentNode = currentNode?.next
count++
}
newNode.prev = currentNode?.prev
currentNode?.prev?.next = newNode
newNode.next = currentNode
currentNode?.prev = newNode
size++
}
}
fun removeLast(): E?{
if (size == 0) throw NoSuchElementException("List is empty")
val removedNode: Node<E>? = lastNode
if (size == 1) {
firstNode = null
lastNode = null
} else {
val prevNode: Node<E>? = lastNode!!.prev
prevNode?.next = null
lastNode = prevNode
}
size--
return removedNode!!.element
}
fun removeLast(index: Int): E? {
//TODO left as an exercise
return null
}
private data class Node<E>(val element: E, var next: Node<E>? = null, var prev: Node<E>? = null)
}
پیاده‌سازی لیست پیوندی (LinkedList) با جاوااسکریپت
زبان جاوااسکریپت یک زبان type-free است، در زیر یک لیست پیوندی رو با جاوااسکریپت پیاده کرده ایم.
class MyLinkedList {
static Node = class {
constructor(element, next = null, prev = null) {
this.element = element;
this.next = next;
this.prev = prev;
}
}
constructor() {
this.firstNode = null;
this.lastNode = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
getSize() {
return this.size;
}
addFirst(element) {
const newNode = new MyLinkedList.Node(element, null, null);
if (this.isEmpty()) {
this.firstNode = newNode;
this.lastNode = newNode;
} else {
this.firstNode.prev = newNode;
newNode.next = this.firstNode;
this.firstNode = newNode;
}
this.size++;
}
addLast(element) {
const newNode = new MyLinkedList.Node(element, null, null);
if (this.isEmpty()) {
this.firstNode = newNode;
this.lastNode = newNode;
} else {
this.lastNode.next = newNode;
newNode.prev = this.lastNode;
this.lastNode = newNode;
}
this.size++;
}
getFirst() {
if (this.isEmpty()) throw new Error("The LinkedList is empty");
return this.firstNode.element;
}
getLast() {
if (this.isEmpty()) throw new Error("The LinkedList is empty");
return this.lastNode.element;
}
get(index) {
if (index < 0 || index >= this.size) {
throw new RangeError(`The index should be between 0 and ${this.size - 1}`);
}
let node;
if (this.size === 1) {
node = this.firstNode;
} else {
let count = 0;
let currentNode = this.firstNode;
while (count !== index) {
currentNode = currentNode.next;
count++;
}
node = currentNode;
}
return node.element;
}
removeFirst() {
if (this.isEmpty()) throw new Error("The list is empty");
let removedNode;
if (this.size === 1) {
removedNode = this.firstNode;
this.firstNode = null;
this.lastNode = null;
} else {
removedNode = this.firstNode;
this.firstNode = this.firstNode.next;
this.firstNode.prev = null;
}
this.size--;
return removedNode.element;
}
add(index, element) {
if (index < 0 || (index >= this.size && this.size !== 0)) {
throw new RangeError("Index out of bounds");
}
if (index === 0) {
this.addFirst(element);
} else {
const newNode = new MyLinkedList.Node(element);
let count = 0;
let currentNode = this.firstNode;
while (count !== index) {
currentNode = currentNode.next;
count++;
}
newNode.prev = currentNode.prev;
currentNode.prev.next = newNode;
newNode.next = currentNode;
currentNode.prev = newNode;
this.size++;
}
}
removeLast() {
if (this.size === 0) throw new Error("List is empty");
let removedNode = this.lastNode;
if (this.size === 1) {
this.firstNode = null;
this.lastNode = null;
} else {
let prevNode = this.lastNode.prev;
prevNode.next = null;
this.lastNode = prevNode;
}
this.size--;
return removedNode.element;
}
remove(index) {
// TODO Left as an exercise
return null;
}
}
پیاده‌سازی لیست پیوندی (LinkedList) با پایتون
پایتون یک زبان type-free است، یعنی نوع متغیر تا زمان مقداردهیش معلوم نیست، در زیر یک لیست پیوندی (LinkedList) رو با پایتون پیاده‌سازی کرده ایم.
class MyLinkedList:
class Node:
def __init__(self, element, next_node=None, prev_node=None):
self.element = element
self.next = next_node
self.prev = prev_node
def __init__(self):
self._first_node = None
self._last_node = None
self._size = 0
def is_empty(self):
return self._size == 0
def get_size(self):
return self._size
def add_first(self, element):
new_node = self.Node(element, None, None)
if self.is_empty():
self._first_node = new_node
self._last_node = new_node
else:
self._first_node.prev = new_node
new_node.next = self._first_node
self._first_node = new_node
self._size += 1
def add_last(self, element):
new_node = self.Node(element, None, None)
if self.is_empty():
self._first_node = new_node
self._last_node = new_node
else:
self._last_node.next = new_node
new_node.prev = self._last_node
self._last_node = new_node
self._size += 1
def get_first(self):
if self.is_empty():
raise ValueError("The LinkedList is empty")
return self._first_node.element
def get_last(self):
if self.is_empty():
raise ValueError("The LinkedList is empty")
return self._last_node.element
def get(self, index):
if index < 0 or index >= self._size:
raise IndexError(f"The index should be between 0 and {self._size - 1}")
if self._size == 1:
node = self._first_node
else:
count = 0
current_node = self._first_node
while count != index:
current_node = current_node.next
count += 1
node = current_node
return node.element
def remove_first(self):
if self.is_empty():
raise ValueError("The list is empty")
removed_node = self._first_node
if self._size == 1:
self._first_node = None
self._last_node = None
else:
self._first_node = self._first_node.next
self._first_node.prev = None
self._size -= 1
return removed_node.element
def add(self, index, element):
if index < 0 or (index >= self._size and self._size != 0):
raise IndexError("Index out of bounds")
if index == 0:
self.add_first(element)
else:
new_node = self.Node(element)
count = 0
current_node = self._first_node
while count != index:
current_node = current_node.next
count += 1
new_node.prev = current_node.prev
current_node.prev.next = new_node
new_node.next = current_node
current_node.prev = new_node
self._size += 1
def remove_last(self):
if self._size == 0:
raise ValueError("List is empty")
removed_node = self._last_node
if self._size == 1:
self._first_node = None
self._last_node = None
else:
prev_node = self._last_node.prev
prev_node.next = None
self._last_node = prev_node
self._size -= 1
return removed_node.element
def remove(self, index):
# TODO Left as an exercise
return None
استفاده از لیست پیوندی در زبان های برنامه نویسی
در بسیاری از زبان های برنامه نویسی لیست پیوندی (LinkedList) به عنوان یک کتابخونه ی استاندارد پیاده‌سازی شده و در اینجا میخوایم استفاده از LinkedList رو بررسی کنیم.
MyLinkedList<String> colors = new MyLinkedList<>();
colors.add("Blue");
colors.add("Pink");
colors.add("Purple");
colors.addFirst("Cyan");
colors.add(1, "Red");
colors.removeLast();
colors.addLast("Yellow");
System.out.println("Display colors ");
for(int i =0; i<colors.size(); i++){
String c = colors.get(i);
System.out.print(c + " ");
}
System.out.println("Remove and Display colors backward: ");
while(!colors.isEmpty()){
String c = colors.removeLast();
System.out.println(c);
}
val colors: MyLinkedList<String> = MyLinkedList<>();
colors.add("Blue")
colors.add("Pink")
colors.add("Purple")
colors.addFirst("Cyan")
colors.add(1, "Red")
colors.removeLast()
colors.addLast("Yellow")
System.out.println("Display colors ");
for(i in 0 until colors.size ){
val c = colors.get(i)
print("$c ")
}
println("Remove and Display colors backward: ")
while(!colors.isEmpty()){
val c = colors.removeLast()
println(c)
}
let colors = new MyLinkedList();
colors.add(0, "Blue"); // Assuming add(index, element) implementation
colors.add(1, "Pink");
colors.add(2, "Purple");
colors.addFirst("Cyan");
colors.add(1, "Red");
colors.removeLast();
colors.addLast("Yellow");
console.log("Display colors ");
for (let i = 0; i < colors.getSize(); i++) {
let c = colors.get(i);
process.stdout.write(c + " ");
}
console.log();
console.log("Remove and Display colors backward: ");
while (!colors.isEmpty()) {
let c = colors.removeLast();
console.log(c);
}
colors = MyLinkedList()
colors.add(0, "Blue")
colors.add(1, "Pink")
colors.add(2, "Purple")
colors.addFirst("Cyan")
colors.add(1, "Red")
colors.remove_last()
colors.add_last("Yellow")
print("Display colors ")
for i in range(0, colors._size):
c = colors.get(i)
print(c + " ", end="")
print()
print("Remove and Display colors backward: ")
while not colors.is_empty():
c = colors.remove_last()
print(c)
خلاصه
- در LinkedList عناصر داخل node ها ذخیره میشن.
- هر node در LinkedList به node بعدی اشاره میکنه.
- انواع پیاده‌سازی LinkedList وجود داره از جمله: Singly LinkedList, Doubly LinkedList و Circular LinkedList
- در Singly LinkedList، یک node به node بعدی اشاره میکنه
- در Doubly LinkedList یک node به node بعد و node قبل از خودش اشاره میکنه (Doubly LinkedList).
- پیچیدگی زمان هنگام افزودن یک عنصر به ابتدا یا انتهای یک LinkedList O(1) و هنگام افزودن یک عنصر با index برابر با O(n) است.
- پیچیدگی زمان برای صدا زدن یک عنصر در LinkedList با index برابر با O(n) است.
- پیچیدگی زمان (time complexity) برای حذف کردن یک عنصر از ابتدا یا انتهای یک LinkedList برابر با O(1) و برای حذف کردن یک عنصر وسط LinkedList برابر با O(n) است.
بازخورد و دیدگاه ها
اولین نفری باشید که در این صفحه نظر می‌دهید